TARDÍGRADOS

Ciencia en español

Posts Tagged ‘función suelo’

Cómo romper los códigos criptográficos RSA: factorizacion de semiprimos y las raices rectangulares

Posted by Albert Zotkin en noviembre 18, 2016

riemann-estela
En la actualidad, usamos algunas de las propiedades de los números primos para codificar mensajes, de modo que ningún intruso pueda leer fácilmente nuestras comunicaciones. Para ello usamos la propiedad siguiente de los número semiprimos: Elegimos dos números primos suficientemente grandes, y obtenemos el semiprimo multiplicándolos. El número semiprimo será parte de la llave pública para nuestro método de encriptación, y con los dos números primos se construyen las llaves privadas. Dado un semiprimo suficientemente grande, es prácticamente imposible hallar en tiempo razonablemente corto, sus dos factores primos. Eso es incluso casi intratable usando supercomputadores. esta dificultad se llama Problema RSA.
Si estás interesado en desencriptar los códigos que protegen el acceso a tarjetas de crédito bancarias o a páginas web seguras, quizás estés interesado en participar en esta clase de Competición de factorización RSA. Veamos un semiprimo catalogado por la RSA y que tiene un premio de 100.000 dólares para quien halle sus dos factores primos. Este semiprimo es el RSA₁₀₂₄, es decir, posee 1024 cifras binarias (309 cifras decimales):

\displaystyle \text{RSA}_{1024} = \\ 13506641086599522334960321627880596993888147560566702752448514385152651060 \\ 48595338339402871505719094417982072821644715513736804197039641917430464965 \\ 89274256239341020864383202110372958725762358509643110564073501508187510676 \\ 59462920556368552947521350085287941637732853390610975054433499981115005697 \\ 7236890927563
Si queremos factorizar con éxito un número semiprimo de la RSA, lo primero que debemos hacer es estimar lo grande que serán sus dos factores primos. Así, para ese RSA₁₀₂₄, los dos factores primos estarán muy cerca relativamente de su raíz cuadrada, es decir, números primos cercanos a las 154 cifras decimales, o lo que es lo mismo, números primos de entre 100 y 200 cifras decimales. Por ejemplo, si uno de los primos resulta tener 120 cifras decimales, el otro estaría muy próximo a las 188. Pero, veamos, ¿cuántos números primos hay que tengan entre 100 y 200 cifras decimables?. Usemos la función contador de números primos, π(x), aproximémosla a x/log(x), porque según Gauss, esa es una buena aproximación para un x suficientemente grande. Así los números primos que tienen entre 100 y 200 cifras decimales son aproximadamente :

\displaystyle 2.17 \times 10^{197}
Supongamos que disponemos del superordenador más potente del mundo, el reciente Sunway TaihuLight, capaz de operar a máximo rendimiento, que es de 125.43 petaFLOPS. Conseguiría resolver el número RSA₁₀₂₄ 1 petaFlop es 1 opración de coma flotando por cada femtosegundo. 10¹⁵ femtosegundos son 1 segundo. En total tardaríamos un maximo de :

\displaystyle 2.17 \times 10^{197} \times 10^{-15} = 2.17 \times 10^{182} \; \text{segundos,}
un tiempo demasiado largo como para tener alguna esperanza de llegar en vida hasta el final del cálculo y verlo con nuestros propios ojos 😛

Veamos ahora qué es una raíz rectangular. Cuando calculamos una raíz cuadrada en realidad estamos calculando dos números, pero como ambos son iguales, no nos damos cuenta que en realidad es un par de números. Por ejemplo, la raices cuadradas de 64 son el par (8, 8):

\displaystyle \sqrt{64}=(8,8)
Podemos calcular para 64 su raices rectangulares, ya que si nos fijamos 64 puede escribirse como 2 elevado a diferentes exponentes, es decir:

\displaystyle 64 = 2^6 = 2^3 \times 2^3 =  2^2 \times 2^4 = 2^1 \times 2^5
Es decir, el número 64 posee dos pares de raíces rectangulares y un par de raíces cuadradas:

\displaystyle 64 = (8,8) = (4,16) = (2,32)
Así, para entendernos, pondremos el par de exponentes de las raices rectangulares entre corchetes, de modo que siempre tendremos la equivalencia:

\displaystyle 1 = \left[\frac{3}{6}, \frac{3}{6}\right] = \left[\frac{2}{6}, \frac{4}{6}\right] = \left[\frac{1}{6}, \frac{5}{6}\right]
Con esto, lo único que estamos haciendo es dividir la unidad en dos partes, de modo que su suma sea esa misma unidad. ¿Por qué el número 64 posee esas raices rectangulare y no otras?. En realidad posee muchas más, pero las que he escrito arriba son las que dan raices enteras. Veamos estos casos:

\displaystyle 64 = 64^{\tfrac{1}{4}}\times 64^{\tfrac{3}{4}}= (2\sqrt{2}) (16\sqrt{2}) \\  64 = 64^{\tfrac{1}{5}}\times 64^{\tfrac{4}{5}}= (2\sqrt[5]{2}) (16\sqrt[5]{2^4}) \\
en general, para cualquier par de número enteros m y n, que sean coprimos,tendremos las raices rectangulares de un número N:

\displaystyle N= N^{\tfrac{m}{n}}\times N^{1-\tfrac{m}{n}}
Veamos ahora cómo aplicamos esto a la factorizaación de números RSA: sean los números primos p = 486023 y q = 598727, por lo que su producto es N = 290995092721. Empezaremos nuestros cálculos con su raíz cuadrada:

\displaystyle \sqrt{N}=539439.60989252541168458987732327730802813682656081\ldots
Igualmente sabemos que ha de ser:

\displaystyle p= N^{\tfrac{m}{n}} \\  q= N^{1-\tfrac{m}{n}}

y puesto que sabemos los valores de p y q, es fácil resolver m y n:

\displaystyle \frac{m}{n}=\frac{\log p}{\log(pq)} \\ \\ \\  1-\frac{m}{n}=1-\frac{\log p}{\log(pq)}=\frac{\log q}{\log(N)}
Por otro lado, si pensamos un poquito, nos daremos cuenta de que factorizar un número RSA no es muy difícil en principio, la dificultad reside en que los números primos, p y q, que forman el semiprimo N, sean muy grandes. Así, es incluso posible presentar una ecuación matemática con la que podemos resolver cualquier número RSA, y es esta:

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor !)=\min (p,q) (1)
Aquí N es producto de los dos primos p y q, mcd es el máximo común divisor de dos números, \lfloor\ r\rfloor ! es el factorial de la parte entera del número real r. Podemos incluso optimizar un poco esa ecuación (1) si usamos el primorial en lugar del factorial,

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor \#)=\min (p,q) (2)
Si N ya es en principio un número muy grande (más de 1024 digitos binarios), el factorial (o el primorial) de la parte entera de su raíz cuadrada será incluso más grande aún, prácticamente intratable. De ahí que las fórmulas (1) y (2) aunque sean correctas, no son muy útiles para el cálculo. En realidad, para calcular un mcd de dos números primero hay que factorizar esos dos números. Es evidente que factorizar N es más fácil que factorizar el primorial de la parte entera de su raíz cuadrada.

Anuncios

Posted in informática, Matemáticas | Etiquetado: , , , , , , , , , , , , , , , , , , , | Leave a Comment »

La función Gamma Γ (x) entra en juego: otra fórmula más que genera números primos

Posted by Albert Zotkin en febrero 26, 2013

La siguiente función, basada en el teorema de Wilson, la cual asigna la unidad si n es número primo y cero si no lo es

\displaystyle  F(n)=\left \lfloor \cos^2 \left ( \cfrac{(n-1)! +1}{n}\right ) \right \rfloor = \begin{cases}  1 & \small \text{si \textit{n}=1 \'o \textit{n} es primo} \\  0 & \small \text{en caso contrario}  \end{cases}  (1)
me abrió los ojos. En realidad, (n-1)! no es más que la función Gamma, \Gamma, Es decir:

\displaystyle  \Gamma(n) = (n-1)!  (2)
Con lo cual (1) también puede expresarse así:

\displaystyle  F(n)=\left \lfloor \cos^2 \left ( \cfrac{\Gamma (n) +1}{n}\right ) \right \rfloor = \begin{cases}  1 & \small \text{si \textit{n}=1 \'o \textit{n} es primo} \\  0 & \small \text{en caso contrario}  \end{cases}  (3)

Pero, la cosa no quedó ahí. Al final, observando un poquito, y haciendo algunas pruebas, pude construir esta otra función, que funciona para n\ge 5 :

\displaystyle  \boxed{Q(x)=\text{frac} \left (\cfrac{\Gamma(x)}{x} \right )\cfrac{x^2}{x-1}= \begin{cases}  x & \small \text{si \textit{x} es primo} \\  0 & \small \text{en caso contrario}  \end{cases}}  (4)
donde \text{frac} es la función parte fraccionaria. Esta función Q(x) tiene dos excepciones, en el intervalo 0<x<5:

\displaystyle  Q(1)=\infty,\ Q(4)=\frac{8}{3}  (5)

ya que los casos Q(2)=2 y Q(3)=3 sí cumplen la definición.

Parecería sorprendente que esta simple función Q(x), la cual mapea tan perfectamente los números primos, sea otra primicia mía, y por lo tanto no me queda otra opción que buscar referencias en la literatura de la historia de las matemáticas, para que nadie me pueda endosar a mi la autoría de tan trivial hallazgo.

Quien aún no esté del todo convencido de que Q(x) funciona puede usar el programa Mathematica, por ejemplo, para computar lo siguiente:

Teorema:
Para todo entero n > 0, con n ≠ 1 y n ≠ 4, si n no es primo, entonces Γ(n) es divisible por n. Lo cual implica que si n es primo, entonces Γ(n) no es divisible por n:

\displaystyle  \small \text{si \textit{n} no es primo, entonces}\\ \\ \Gamma (n) \equiv 0 \pmod n  (6)

Posted in Matemáticas | Etiquetado: , , , , , , | 2 Comments »

Una fórmula que calcula el n-ésimo número primo

Posted by Albert Zotkin en febrero 25, 2013

El Teorema de Wilson dice que si p es un número primo, entonces (p-1)! + 1 es múltiplo de p. Es decir:

\displaystyle  (p-1)! \equiv -1 \mod{p}  (1)

Basándomos en este teorema es posible construir una función tal que:

\displaystyle  F(n)=\left \lfloor \cos^2 \left (\pi \cfrac{(n-1)! +1}{n}\right )  \right \rfloor = \begin{cases}  1    & \small \text{si \textit{n}=1 \'o \textit{n} es primo} \\  0 & \small \text{en caso contrario}  \end{cases}   (2)
donde \lfloor x \rfloor es la función suelo. Pero, es precisamente esta función suelo lo que menos me gusta de esta fórmula (2). Por lo tanto, la pregunta es si es posible modificar esa función (2) tal que no aparezca ningún tipo de función suelo o función techo. La respuesta es sí. Fijémonos en la siguiente función, para n \ge 1:

\displaystyle  G(n)=\sin^2 \left (\pi \cfrac{(n-1)! +1}{n} \right )  = \begin{cases}  \sin^2 (\frac{\pi}{n})    & \small \text{si \textit{n} no es primo} \\  0 & \small \text{si \textit{n} es primo}  \end{cases}   (3)
Es decir, para n \ge 1 la función G(n) nos da la secuencia

\displaystyle   G(n)= \left \{0,\ 0,\ 0,\ \cfrac{1}{2},\ 0,\ \cfrac{1}{4},\ 0,\ \sin^2\left(\cfrac{\pi }{8}\right),\ \sin^2\left(\cfrac{\pi }{9}\right),\ \cfrac{1}{16} \left(-1+\sqrt{5}\right)^2, \ \dots \right \}  (4)
Por lo tanto, sólo tenemos que dividir G(n) por \sin^2 \pi/n , para obtener :

\displaystyle  H(n)=\cfrac{\sin^2 \left ( \pi \cfrac{(n-1)! +1}{n} \right )}{\sin^2 \frac{\pi}{n}}  = \begin{cases}  1    & \small \text{si \textit{n} no es primo} \\  0 & \small \text{si \textit{n} es primo}  \end{cases}   (5)

Es decir, ya que para n=1 da indeterminado, para n \ge 2 la función H(n) nos da la secuencia

\displaystyle  H(n)= \left \{0,\ 0,\ 1,\ 0,\ 1,\ 0,\ 1,\ 1,\ 1, \ \dots \right \}  (6)

Pero si lo que estamos buscando es la función

\displaystyle   P(n)= \begin{cases}  0    & \small \text{si \textit{n} no es primo} \\  1 & \small \text{si \textit{n} es primo}  \end{cases}   (7)

Sólo tenemos que establecerla como complementaria de H(n):

\displaystyle   \boxed {P(n)= 1- H(n) = 1 - \cfrac{\sin^2 \left (\pi \cfrac{(n-1)! +1}{n} \right )}{\sin^2 \frac{\pi}{n}}}  (8)

con lo cual hemos obtenido una función similar a F(n), pero sin la función suelo.



Algunos consejos para su uso en Mathematica

Define la función que genera la lista (cero si no es número primo), por ejemplo esta función :
  

In[1]:=

Define ahora la función que quitará los ceros, por ejemplo esta :

In[2]:=

Veamos ahora algunos ejemplos. Primero veamos cómo la función F[x] genera una lista de números primos :

In[3]:=

Out[3]=

Veamos ahora un ejemplo de cómo la función P[x] quita los ceros . Pero, antes de eso quiero advertir que la función P[x] es muy ineficiente para esa tarea (tarda mucho) y sólo debe ser considerada como una curiosidad matemática, nada más. Aconsejo no usarla en calculos prácticos con Mathematica. Por lo tanto, como muestra, sólo la usaré para un cálculo hasta n=10:

In[4]:=

Out[4]=

Para quien posea curiosidad por saber cúanto tiempo tarda Mathematica en hacer esta última tarea, haré lo siguiente :

In[5]:=

Out[5]=

Lo cual significa que esta última operación ha tardado unos 20 segundos en realizarse (una velocidad muy pobre si tenemos en cuenta que sólo calculó hasta n = 10).

Pero, si aún deseamos quitar eficientemente los ceros a la lista que genera la función F[x], podemos usar el algoritmo Deletecases, así:

In[6]:=

Out[6]=


Otros ejemplos de funciones generadoras:

In[9]:=

In[11]:=

Out[11]=

In[12]:=

In[13]:=

Out[13]=

Posted in Matemáticas | Etiquetado: , , , , | 4 Comments »

 
A %d blogueros les gusta esto: