Búsqueda de números primos gigantes.

Escrito por Manuel el marzo 5, 2012

Llevo un tiempo comentando en twitter mi pasión por los números y las finanzas y todo lo relacionado con la valoración de cualquier producto financiero por medio de métodos numéricos, como por ejemplo la valoración de opciones europeas y de algunas exóticas.

Además de realizar cálculos financieros soy un apasionado de los matemáticas y cualquier algoritmo en el que se tenga que utilizar la computación y por eso he rescatado mis apuntes de la asignatura seguridad en la información en los que tenía una serie de algoritmos probabilísticos que demuestran si un número es primo o no, de forma que se calculaban 3 números primos r, p y q que cumplían las siguientes condiciones:

– Si r es primo y p=(2*r)+1 y q=(2*p)+1 y p y q son también primos.

Estos números primos pueden ser utilizados para el algoritmo de encriptación RSA. El que cumplan que q = (2*p)+1 hace que el algoritmo sea muy fuerte y casi imposible de factorizar un número n que es producto de p y q (siempre hay que decir casi).

El objetivo de este POST no es mostrar en qué consiste RSA ya que habrá muchísima gente que sea mucho mejor explicando en qué consiste este algoritmo pero yo os voy a presentar 3 algoritmos que demuestran si un número es primo o no y luego un pequeño programa que utiliza uno de ellos para encontrar tres números primos con las características que he descrito anteriormente.

El objetivo es calcular un trío de números primos y que sean gigantes, lo ideal es que tengan más de 100 cifras cada uno.

He utilizado el programa MATHEMATICA en lugar del habitual MATLAB ya que la gestión de números gigantes es mucho más eficiente en Mathematica que en Matlab.

DESCRIPCIÓN DE LOS ALGORITMOS UTILIZADOS:

  •   Teorema del Número Primo (Tchebycheff):

  • Teorema:

  •   Test de Miller:

Las funciones con los algoritmos propuestos que he desarrollado están incluidas en los ficheros Tchebycheff.nb, Teorema.nb y Miller.nb. Estas funciones tienen un bucle en el que se estudia la primalidad del número 10 veces.

Para el cálculo de los 3 primos r, p y q he programado una sencilla función que termina cuando encuentra estos tres números primos que cumplen las condiciones descritas al principio del post. La función empieza a buscar a partir de una semilla que es introducida como parámetro de la función. Recomiendo poner una semilla de 100 dígitos por ejemplo para asegurarnos de que los primos encontrados son superiores a esa longitud. La función se encuentra en el fichero Busca_Primos.nb y utiliza el segundo algoritmo explicado, es decir, el del fichero Teorema.nb. He descartado que haga el test 10 veces porque el tiempo de ejecución sería mucho más alto. Todas las funciones se encuentran en el ZIP que incluyo al final del POST.

Me encantaría tener un ordenador más potente del que tengo porque me hubiera atrevido a encontrar primos de 200 cifras. Hay que tener en cuenta que si no encuentra estos números el algoritmo no termina, así que cuidado.

Estos conjuntos de 3 primos son los que he encontrado yo por ahora:

PRIMOS

El mundo de los números primos es apasionante, por lo menos así lo veo yo.

Siempre se puede aplicar la función PRIMEQ de Mathematica que nos verifica si el número es primo o no, hay que tener en cuenta que los algoritmos son probabilísticos tipo de Montecarlo.

Primos_Gigantes

 

5Mar