TARDÍGRADOS

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

Posts Tagged ‘función contador de números primos’

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.

Anuncios

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

Expansiones naturales completas de los productos de Euler

Posted by Albert Zotkin en septiembre 11, 2016

Hola amigos de Tardígrados. Siguiendo esta secuencia matemática, hoy vamos a ver cómo expresar un Producto de Euler, de tal forma que el índice del producto corra no únicamente sobre todos los números primos, sino sobre los sucesivos números naturales.

El primer caso que vamos a ver es el Producto de Euler asociado a función Zeta de Riemann. Este producto es:

\displaystyle \prod _{p}(1-p^{-s})^{-1}=\prod _{p}{\Big (}\sum _{n=0}^{\infty }p^{-ns}{\Big )}=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\zeta (s) (1)
donde el índice del producto corre sobre los sucesivos números primos. Ahora, aprovechando la función característica de los números primos que os presenté en el artículo anterior, vamos a ver cómo es posible hacer que el índice de ese producto infinito (porque sabemos que hay infinitos números primos) corra ahora sobre los sucesivos números naturales. Y la respuesta es simplemente esta:

\displaystyle \prod_{p}(1-p^{-s})^{-1}=\prod_{n=1}^{\infty}(1-\chi _{{{\mathbb  {P}}}}(n)n^{-s})^{-1}=\zeta (s) (2)
donde obviamente ?P es la función característica de los números primos. Una forma inédita de expresar la función zeta de Riemann, parece, y descubierta por mi 😛 Vemos también, que puesto que sabemos usar la función característica de los números compuestos (los números no primos), es posible definir una nueva función zeta relacionada con ellos, así:

\displaystyle \zeta_{NP} (s)=\prod_{n=2}^{\infty}(1-\chi _{{{\mathbb  {NP}}}}(n)n^{-s})^{-1} (3)
donde es más que obvio que la función caracteristica ?NP es la de los números no primos. Y llegamos a la conclusión de que la función zeta de Riemann y esta ?NP están relacionadas por medio de algún tipo propiedad de complementariedad, que todavía no vislumbro. Esta peculiar función zeta ?NP posee un polo en n = 1, por eso el índice del producto empieza a correr desde n = 2. Y lo primero que advertimos en la evaluación de dicha función es el notable y absolutamente increible resultado siguiente:

\displaystyle \zeta_{NP} (2)= \frac{2}{\zeta(2)}= \frac{12}{\pi^2} (4)

Saludos

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

Conexión entre la Conjetura de Kepler y los números primos através de la Constante tridimensional de Hermite

Posted by Albert Zotkin en septiembre 10, 2016

Hola amigos de Tardígrados. Hoy os voy a presentar un espectacular hallazgo matemático hecho por mí hoy mismo. Os lo presento sin dilación ya mismo:

\displaystyle \sum_{i=1}^\infty \cfrac{(-1)^{\pi(i)-\pi(i-1)}}{i^2}= \frac{\pi}{3\sqrt{2}} (1)
donde π(x) es la función contador de números primos, no confundir con el número irracional trascendente π, el cual aparece en el lado derecho de la fórmula. Es decir, esa función contador nos dice cuántos número primos hay desde 0 hasta el número real x. La identidad que he hallado es simplemente la Constante de Hermite en tres dimensiones, o al menos se le aproxima mucho, pues esa fórmula la he comprobado hasta el término i = 1000000. Parece converger rápidamente hacia ese limite.

Respecto a la función contador de números primos expresada como diferencia:

\displaystyle \chi _{{{\mathbb  {P}}}}(n)=\pi(n)-\pi(n-1)

nos define exactamente una función característica χP(n) de números primos, es decir, una función tal que si n es primo entonces esa función es χP(n) = 1, y en caso contrario es χP(n) = 0.
En cuanto al número

\displaystyle  \frac{\pi}{3\sqrt{2}} = 0.740480489693061041169313495\dots

que es la llamada Constante de Hermite en tres dimensiones, es simplemente, la máxima densidad que se puede alcanzar empaquetando esferas tridimensionales, tal como se explica en la Conjetura de Kepler.

De igual forma que hemos definido una función característica de los número primos, también podemos definir una para los números no primos, es decir, para los números compuestos, así:

\displaystyle \chi _{{{\mathbb  {NP}}}}(n)=1-\pi(n)-\pi(n-1)

La función caracteristica χP(n) define una sucesión de ceros y unos, por lo que podemos considerar que representa a un número real expresado en sistema de numeración de base 2. Si la coma de ese número decimal la ponemos entre el primer digito a la izquierda y el siguiente tendremos en dicha base 2 el número:

\displaystyle \rho' =0.011010100010100010100010000\ldots _{2}

el cual, en base 10, se expresaría así:

\displaystyle \rho' =0.414682509851111660248109622\ldots

A este número real, el cual es fácil demostrar que es un número irracional, se le llama Constante Prima, y puede ser definida asi:

\displaystyle \rho' =\sum _{{p}}{\frac  {1}{2^{p}}}=\sum _{{n=1}}^{\infty }{\frac  {\chi _{{{\mathbb  {P}}}}(n)}{2^{n}}}

Podemos hacer lo mismo con los números compuestos y obtener la constante de los números compuestos asi:

\displaystyle \rho =\sum _{{n=1}}^{\infty }{\frac  {\chi _{{{\mathbb  {NP}}}}(n)}{2^{n}}} =0.085317490148888339751890377845692291634\ldots

Es fácil ver que \rho +\rho'=1/2. Pero, toda esta presentación de estas dos funciones características complementarias viene porque, al igual que hice al principio presentando la identidad (1), ahora también puedo hacer lo mismo, pero con la función caracteristica de los no primos, y obtenemos:

\displaystyle \sum_{i=1}^\infty \cfrac{(-1)^{\chi _{{{\mathbb  {NP}}}}(i)}}{i^2}= \sum_{i=1}^\infty \cfrac{(-1)^{1-\pi(i)-\pi(i-1)}}{i^2}=-\frac{\pi}{3\sqrt{2}} (2)
Intentemos ahora simplificar un poco las identidades (1) y (2). Fijémonos que podemos expresar

\displaystyle (-1)^{\chi _{{{\mathbb  {P}}}}(i)}= 1- 2 \chi _{{{\mathbb  {P}}}}(i) (3)
por lo que (1) puede ser escrita así:

\displaystyle \sum_{i=1}^\infty \cfrac{(-1)^{\chi _{{{\mathbb  {P}}}}(i)}}{i^2}= \sum_{i=1}^\infty \cfrac{1- 2 \chi _{{{\mathbb  {P}}}}(i)}{i^2}=
\displaystyle =\sum_{i=1}^\infty \cfrac{1}{i^2}- 2 \sum_{i=1}^\infty \cfrac{\chi _{{{\mathbb  {P}}}}(i)}{i^2} \\ \\ \\  \sum_{i=1}^\infty \cfrac{1}{i^2} =\zeta(2)=\frac{\pi^2}{6} \\ \\ \\  2 \sum_{i=1}^\infty \cfrac{\chi _{{{\mathbb  {P}}}}(i)}{i^2} = 2 \sum_{i=1}^\infty \cfrac{i\chi _{{{\mathbb  {P}}}}(i)}{i^3}=2 \sum_p \cfrac {p}{\pi(p)^3}
Por lo que, si la conjetura es cierta, tendremos que el siguiente sumatorio, que corre a lo largo de los infinitos números primos, está bastante relacionado con el número π:

\displaystyle \sum_p \cfrac {p}{\pi(p)^3} = \frac{\pi ^2-\pi \sqrt{2}}{12} (4)
donde, obviamente, π(p) es la función contador del número primo p, es decir, el orden que ocupa ese número primo en la sucesión de números primos.

Desafortunadamente la conjetura es falsa, ya que como demuestro en esta pregunta en math.stackexchange,

\displaystyle \sum_{i=1}^\infty \cfrac{(-1)^{\chi _{{{\mathbb  {P}}}}(i)}}{i^2}= \sum_{i=1}^\infty \cfrac{1- 2 \chi _{{{\mathbb  {P}}}}(i)}{i^2} = \sum_{i=1}^\infty \cfrac{1}{i^2}- 2 \sum_{i=1}^\infty \cfrac{\chi _{{{\mathbb  {P}}}}(i)}{i^2} = \\ \\ =\zeta(2)-2 \sum_p \cfrac{1}{p^2} = \zeta(2)-2 P(2)= \\ \\ \\ = 0.7404392267660954394593\ldots
donde P(2) es la función zeta prima de 2. Porque,

\displaystyle \frac{\pi}{3\sqrt{2}}\neq \zeta(2)-2 P(2)

y efectivamente,

\displaystyle \frac{\pi ^2 -\pi \sqrt{2}}{12}<P(2)

Saludos

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

 
A %d blogueros les gusta esto: