sábado, 19 de julio de 2014

Riemann, números primos y computación

La búsqueda de los números primos
A finales de 1859 se produce en la Universidad de Göttingen la publicación de un artículo titulado "Über die Anzahl der Primzahlen unter einer gegebenen Grösse" ("Sobre el número de números primos menores que uno dado") que abriría la caja de pandora sobre la búsqueda de un patrón para los números primos. El autor de ese artículo fue Riemann, que lo escribió como agradecimiento a la Academia de Berlin por haberlo aceptado como miembro.
La distribución de los números primos es un problema que se remonta alrededor del año 300 a. C con Euclides, pues suya es la primera mención que se conoce del teorema fundamental de la aritmética: Todo número entero puede ser escrito como producto único de números primos.
Demostración de Euclides
Por todos es conocido la demostración de Euclides de la infinitud de los números primos, que dada su belleza escribiré brevemente:
Supongamos que hay un número finito de número primos:
2, 3, 5, 7,\cdots,p, p_1, p_2, \cdots p_n
Ahora consideramos el producto de todos ellos más uno:
2 \cdot 3 \cdot 5 \cdot 7 \cdots p \cdot p_1 \cdot p_2 \cdots p_{n+1}
Al dividir este nuevo número por cada uno de los primos obtenemos siempre resto 1.
P:2=2 Q_1 + 1
P:3=3 Q_2 + 1
P:5=5 Q_3 + 1
\vdots
Por tanto, debe de ser también primo o divisible por un primo que no aparecía en la lista inicial. Lo cual es absurdo pues en nuestra lista inicial estaban todos los primos, por tanto el número de primos ha de ser infinito.
El tema permaneció olvidado hasta la Edad Media, cuando Fermat compró una edición de la Arithmetica de Diofanto, publicada en en 1.621 por Claude Bachet de Méziriac. Éste libró despertó la curiosidad de Fermat, que rápidamente comenzó a estudiar hasta dominar todos sus resultados.
Fermat, sin duda, fue el iniciador de la moderna teoróa de números. Hasta entonces, los resultados sobre números eran meras curiosidades o casualidades, Fermat sistematizó el estudio de las propiedades de los números. Además contribuyó notablemente a su desarrollo, pues aunque Fermat realizó gran cantidad de afirmaciones, que comunicada en cartas enviadas a grandes matemáticos, muy pocas fueron sus demostraciones. En la publicación de la Arithmetica de Diofanto que realizó su hijo en 1670 se puede observar que Fermat no realizó ninguna demostración de sus resultados. Muchos matemáticos dedicarían gran parte de sus investigaciones a comprobar los resultados de Fermat.
Después de Fermat, el siguiente matemático que impulsó la teoría de números fue Euler, que introdujo una nueva herramienta en el estudio de los números: la series infinitas. Euler comenzó a estudiar teoría de números estando de suplente en la Academia de Ciencias de San Petersburgo. Allí recibe una carta de Goldbach invitándole a pronunciarse sobre el siguiente enunciado de Fermat: los númerosson primos para cualquier valor natural de n.
Hacia 1737, Euler, en su artículo “Variae observationes circa series infinitas”, comienza a utilizar las series númericas en sus investigaciones. El artículo comienza con la serie:
\displaystyle \frac{1}{15}+ \frac{1}{63}+ \frac{1}{89}+\frac{1}{255}+ \cdots
pero muy pronto sus investigaciones le conducen a los números primos, en concreto en la serie armónica
\displaystyle \sum_{n=1}^{\infty} \frac{1}{n}
. Euler probó que
\displaystyle \sum_{n=1}^{\infty} \frac{1}{n} = 1 + \frac{1}{2}+\frac{1}{3}+ \frac{1}{4}= \frac{ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdots }{1 \cdot 2 \cdot 4 \cdot 6 \cdot 10 \cdot 13 \cdots
cuya fracción esta formada por los números primos en el denominador y los primos menos una unidad en el denominador.
Euler mostró una relación que atraparía a muchos matemáticos futuros: los inversos de los números naturales con los números primos:
\sum_{n=1}^{\infty} \frac{1}{n}= \prod_{p} \frac{1}{1 - \frac{1}{p}}
con n natural y p primo.
De hecho, Euler hizo más y generalizó el resultado:
\sum_{n=1}^{\infty} \frac{1}{n^s}= \prod_{p} \frac{1}{1 - \frac{1}{p^s}}
. Y este resultado es el inicio del artículo de Riemann.
Después de Euler continuó Legendre, que en su “Ensayos sobre la teoría de los números” realizó importantes avances. En él, Legendre se aventura a dar una expresión analítica para la función que expresa el número de números primos menores que x. La aproximación que dio fue:
\pi(x)= \frac{x}{ln x - 1,08366}
Es la primera vez que aparece una expresión analítica para  \pi(x)
Más tarde, como no podía ser de otra manera llegó Gauss y afinó aún más la función  \pi(x)escribiendo en una carta que él había conseguido aproximarla a  \frac{x}{ln x .
Otro matemático que influyó en el artículo de Riemann fue Dirichlet, amigo personal suyo. Dirichlet es un matemático mucho más conceptual y ante la función pensó ¿por qué limitarse simplemente a los números naturales? ¿qué sucedería si tomáramos el cuerpo de los números reales como dominio?
La idea de Dirichlet no estaba tan descaminada, ya que al usar los números reales se ponía a disposición de los matemáticos todo el campo del análisis.
Con estos y algún otro precedente, Riemann tiene la genial idea de considerar  \zeta(s)= \sum_{n=1}^{\infty} \frac{1}{n^s} como función de variable compleja s. El objetivo de Riemann era demostrar que  \frac{x}{ln x  a través de la función  \zeta(x)  vista su estrecha relación con los números primos dada por la fórmula de Euler.
Aunque no logró su objetivo, la gran cantidad de resultados que encontró en su camino iluminaron a muchos matemáticos entre ellos a Littlewood y Hardy.
RSA
Hoy en día día, en el mundo de las tecnologías, los ordenadores e internet, la conjetura que lanzó Riemann sobre los números primos adquiere un valor especial. 
En 1977, Rivest, Shamir y Adelman crean el sistema de encriptación de clave pública, el RSA (iniciales de sus creadores), basado en los números primos y en la dificultad de entrar la descomposición factorial de un número cualquiera.

El RSA consta de dos claves: una pública, que todo el mundo conoce, y otra privada. La base del sistema creado por Rivest, Shamir y Adelman son los números primos y la dificultad para encontrar la descomposición factorial de un numero cualquiera.
Tomando dos números primos p y q, generamos  n = p \cdot q
Usando la función de Euler \phi , que nos da el número de números primos con n, menores o iguales a n, obtenemos \phi(n) .
\phi(n)= \phi(p \cdot q)= (p-1)\cdot(q-1)
Para generar la clave pública buscamos un número primo con \phi(n) y menor que \phi(n) . A este número le llamamos e. El siguiente paso es encontrar un número, que normalmente se desgina con la letra d, de forma que su producto con e se pueda dividir entre \phi(n) dando como resto 1, es decir, que d · e -1 sea divisible entre \phi(n) , o como diría Gauss  d=e^{-1} mod \ph(n) , d es el inverso modular de e mod \phi(n) .
Como resultado obtenemos dos números e y d que nos permitirán crear nuestro sistema de encriptación. ¿Cómo encriptar con este método?
El texto cifrado, C, de un mensaje de texto normal P, se transmite por la regla:
C=P^e (mod n)
El texto cifrado lo descifra el receptor de acuerdo a la regla:
P = C^d (mod n)
Veamos un ejemplo:
Tomemos  p=3, q=11 y n=33
Por tanto, \phi(33)=20  y  z=20  y por tanto un número tal que el  m.c.d.(20,e)=1  pueder 7. Así $e=7
Buscamos ahora un número tal que  7 \cdot d -1=20. Este número es 3, por tanto d=3.
Con estos número ya tenemos nuestro sistema de encriptación:
Si queremos encriptar la palabra HOLA. tenemos.
El emisor construye la siguiente tabla:
La información que trasmite es: 17 09 12 01.
El receptor tiene una tabla parecida:

Los números e y d tienen una particularidad muy especial, si utilizo e como exponente, obtengo un número que al aplicarle el mismo algoritmo pero con d como exponente, me da el número original. De esta forma ya tenemos nuestra pareja de claves. El par (e, n) sería la clave pública, y el par (d, n) sería la clave privada.
En nuestro ejemplo, con e=3 y n=33 codifico y solo aquel que tenga la clave privada d=7 y n=33 podrá descodificarlo.
Si alguien quisiera averiguar nuestro mensaje solo dispondría del mensaje cifrado y la clave pública (e, n). Para descifrarlo necesitaría conocer d, es decir, el exponente secreto con la propiedad de que e · d es congruente con 1 módulo \phi(n) . Por tanto, para hallar d tiene que averiguar el inverso modular de e mod \phi(n) , para lo cual tiene dos opciones:
- Averiguar cuantos factones no tienen factores comunes con n, cosa que no sabe.
- Factorizar n.

La seguridad de este sistema estriba en que el número \phi(n) (en nuestro ejemplo 20) es desconocido para el usuario. Si descubrimos un metodo para encontrar \phi(n) podríamos descifrar el sistema de encriptación, pues tanto e como d están basado en \phi(n) . Pero a día de hoy el único método posible para encontrar \phi(n) es factorizar n = p · q. Esto es precisamente lo que da seguridad al sistema, eligiendo p y q suficientemente grandes (hoy en día se manejan números de 1024 bits con unas 300 cifras decimales), se hace imposible factorizar p · q en un tiempo razonable. Pero, ¿qué sucedería si apareciese una forma rápida de factorizar n = p · q?
RSA-640
El 8 de noviembre de 2005 un equipo en la Agencia Federal Alemana para la Seguridad en TecnologÍa de la Información (BSI) anunció la factorización del número de 193 dígitos:
310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609
conocido como RSA-640, ya que en código binario tiene 640 cifras. Para ello necesitaron 80 ordenadores Opteron 2,2 Ghz trabajando conjuntamente durante 3 meses.
TOMADO DE: http://dem.fespm.es/dia-escolar-de-las-matematicas/la-computacion-en-la-investigacion/article/riemann-numeros-primos-y
Publicado por en No hay comentarios:
Etiquetas:
Suscribirse a: Entradas (Atom)

Archivo del blog