TARDÍGRADOS

Ciencia en español -ʟᴀ ʀᴀᴢóɴ ᴇsᴛá ᴀʜí ғᴜᴇʀᴀ-

Posts Tagged ‘raíz cuadrada’

Más allá del último Teorema de Fermat

Posted by Albert Zotkin en marzo 4, 2018

Hola amigo incondicional de Tardígrados. Anoche. como no podía conciliar el sueño, en lugar de contar ovejitas, me puse a calcular mentalmente ternas pitagóricas, y de ahí pasé a mayores evocando el último Teorema de Fermat. Afortunadamente me quedé dormido pronto, pero de todo eso surgieron algunas ideas extravagantes, que más se parecen a cabezonería que a otra cosa. Y me dije para mis adentros: “vale, vale, el último Teorema de Fermat es cierto, no es posible encontrar ternas de números enteros positivos (x, y, z) tal que se cumpla la relación:

\displaystyle    x^n + y^n = z^n  \, (1)
para todo n > 2. Pero, ¿y si nos emperramos en que esa relación se pueda cumplir para ciertas ternas de enteros positivos?. Es decir, queremos que “el último Teorema de Fermat sea falso“, entre comillas, por supuesto. Queremos ir mas allá. Pensemos por un momento en algo parecido a lo que queremos conseguir. Ese algo puede ser, por ejemplo, la raíz cuadrada de un número real negativo. Por mucho que nos empeñemos, la raíz cuadra de un número real negativo no es un número real, ni negativo ni positivo. Pero alguien se emperró y dijo hacia sus adentros, ¿cómo que no voy a ser capaz de calcular esto?:

\displaystyle    x = \sqrt{-25} (2)
Para poder resolver esa imposibilidad algebraica se inventaron los números complejos, y más concretamente el número imaginario i = (0, 1), del cual queremos que su cuadrado sea igual a -1. De esa forma tan artificial y forzada tendremos que, efectivamente:

\displaystyle    x = \sqrt{(-1)25 } =\sqrt{-1}\sqrt{25}= i\sqrt{25} \\ \\ i =\sqrt{-1} (3)
¿Hemos resuelto el problema?. No, pero hemos sabido encapsular el objeto conflictivo, aislarlo de la solución. Los números complejos, visto de esta forma tan extravagante, son como hacer limpieza y meter toda la basura debajo de la alfombra. En realidad, no hemos resuelto el problema de la raíz cuadrada de un numero negativo, simplemente hemos escondido el problema debajo de la alfombra. Pero, al hacer eso, nos hemos visto forzados a definir una nueva clase de números, los números complejos, de la que los números reales es simplemente un subconjunto. Así, con la ecuación (1), que define el teorema de Fermat, pasa algo muy parecido. Supongamos que queremos que exista una solución de ternas enteras para

\displaystyle   x^3 + y^3 = z^3  \, (4)
Sabemos que no será una solución real. Busquemos ternas de números que podrían servirnos. Y para ello nos basaremos en un método análogo al que utilizó Euclides para encontrar ternas Pitagóricas. Euclides encontró, para para cualquier par aleatorio de números enteros positivos, m y n, con m > n, que es posible definir una terna que cumpla el Teorema de Pitágoras, así;

\displaystyle  x=m^{2}-n^{2},\ \,y=2mn,\ \,z=m^{2}+n^{2} (5)
y la relación del Teorema de Pitágoras se cumplirá siempre si las ternas están definidas de esa forma, para cualquiera que sean los números aleatorios m y n:

\displaystyle  z^2=x^2+y^2 (6)
Hagamos ahora algo parecido para nuestras ternas de Fermat en la relación cúbica. Es decir, desde dos números aleatorios m y n, definamos nuestras ternas así:

\displaystyle  x=m^3-n^3,\ \,y=\sqrt[3]{2n^9+ 6m^6 n^3},\ \,z=m^3+n^3 (7)
Evidentemente, como el último Teorema de Fermat es cierto, no esperamos que nuestras ternas, definidas de esa forma, cumplan la relación cúbica (4). Pero, las vamos a presentar para a ver qué ocurre:

\displaystyle  x^3+y^3= (m - n)^3+\left(\sqrt[3]{2n^3+ 6m^2 n}\right)^3 = \\ \\  =(m^3 - n^3)^3+ (2n^9+ 6m^6 n^3)^3 = m^9+3 m^6 n^3+3 m^3 n^6+n^9 = \\ \\   =(m^3+n^3)^3=z^3 (8)
Con lo cual hemos demostrado que el último Teorema de Fermat es ¡falso!. ¿Dónde está el error?. El error está en afirmar que, tal y como hemos definido y, desde los enteros positivos aleatorios m y n, debe ser obligatoriamente un entero positivo. De hecho para demostrar que el último Teorema de Fermat es cierto para el caso cúbico basta con demostrar que:

\displaystyle  y =\sqrt[3]{2n^9+ 6m^6 n^3}  (9)
no puede ser entero positivo si m y n lo son. Y eso se demuestra muy rápidamente:

\displaystyle  y^3 = 2n^9+ 6m^6 n^3 (10)
no puede ser un cubo porque el único sería:

\displaystyle  y^3 = n^9+ 6n^9  +  n^9 = 8 n^9 \\  y = 2n^3 (11)
que es una contradicción ya que originalmente m no puede ser igual a n. En general, para demostrar este teorema para todos los casos, basta con demostrar que el número y no puede ser entero si n y m son enteros. El caso general más simple sería:

\displaystyle  x= m-n ,\ \, z= m+n \\ \\  y = \sqrt[k]{(m+n)^k - (m-n)^k } (12)
y como sabemos que las siguientes expansiones son ciertas:

\displaystyle (m+n)^k = \sum_{j=0}^k {k \choose j} m^{k-j}n^j \\ \\ \\ (m-n)^k = \sum_{j=0}^k {k \choose -j} m^{k-j}n^j (13)

tendremos que:

\displaystyle  (m+n)^k -(m-n)^k = \sum_{j=1}^{k-1} {k \choose j} m^{k-j}n^{j} -\sum_{j=1}^{k-1} {k \choose -j} m^{k-j}n^{j} \\ \\ \\ (14)
Es decir, el número y, expresado desde los aleatorios enteros positivos m y n, sería:

\displaystyle  y = \sqrt[k]{\sum_{j=1}^{k-1} {k \choose j} m^{k-j}n^j-\sum_{j=1}^{k-1} {k \choose -j} m^{k-v}n^j} \\ \\ \\ (15)
Con lo cual para demostrar que es cierto el último Teorema de Fermat, basta con demostrar que, en esta última ecuación (14), si m y n son enteros positivos, entonces y no lo es, y eso debe ser cierto para todo k entero positivo.

El caso general algo menos simple que el anterior sería:

\displaystyle  x= m^k-n^k ,\ \, z^k= m^k+n^k \\ \\  y = \sqrt[k]{(m^k+n^k)^k - (m^k-n^k)^k } (16)
Pero, las expansiones son muy parecidas a las del caso anterior, sólo hay que elevar a k los dos factores que acompañan al binomial, porque es simplemente un vulgar cambio de variable:

\displaystyle y = \sqrt[k]{\sum_{j=1}^{k-1} {k \choose j} m^{k^2-j k}n^{v k} -\sum_{j=1}^{k-1} {k \choose -v} m^{k^2-j k}n^{j k} } (17)
Esa diferencia de sumatorios es fácil redcirla, ya que poseen sumandos iguales, pero en el segundo sumatorio hay alternancia de signos ±. Por lo tanto, los sumando en posiciones impares se suman duplicándose, y los de posiciones pares se restan, anulándose. Una forma elegante de expresar esa diferencia de sumatorios es esta:

\displaystyle y = \sqrt[k]{\sum_{j=1}^{k-1} {k \choose j} (1+e^{i \pi j}) m^{k^2-j k}n^{j k} }

(18)
El último Teorema de Fermat viene a decirnos que el único caso para el que el número y resulta ser entero, siendo los aleatorios enteros m y n, es cuando k = 2. Los casos para k >2, dan todos un número y que no es entero, es decir, le sobra o le falta siempre cierta cantidad para completar un hipercubo.

\displaystyle k=2,\,y= 2 \sqrt{m^2 n^2} \\   k=3,\,y= \left(6 m^6 n^3+2 n^9\right)^{1/3} \\   k=4,\,y= \left(8 m^{12} n^4+8 m^4 n^{12}\right)^{1/4} \\   k=5,\,y=  \left(10 m^{20} n^5+20 m^{10} n^{15}+2 n^{25}\right)^{1/5} \\  k=6,\,y= \left(12 m^{30} n^6+40 m^{18} n^{18}+12 m^6 n^{30}\right)^{1/6} \\   k=7,\,y= \left(14 m^{42} n^7+70 m^{28} n^{21}+42 m^{14} n^{35}+2 n^{49}\right)^{1/7} \\  k=8,\,y= \left(16 m^{56} n^8+112 m^{40} n^{24}+112 m^{24} n^{40}+16 m^8 n^{56}\right)^{1/8} \\  k=9,\,y=  \left(18 m^{72} n^9+168 m^{54} n^{27}+252 m^{36} n^{45}+72 m^{18} n^{63}+2 n^{81}\right)^{1/9} \\  k=10,\,y=  \left(20 m^{90} n^{10}+240 m^{70} n^{30}+504 m^{50} n^{50}+240 m^{30} n^{70}+20 m^{10} n^{90}\right)^{1/10}

Anuncios

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

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 RSA1024, 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 RSA1024, 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, p(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 RSA1024 1 petaFlop es 1 opración de coma flotando por cada femtosegundo. 10¹5 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.

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

 
A %d blogueros les gusta esto: