Hallado un número primo de más de 17 millones de cifras

Hace unos días se ha descubierto último primo de Mersenne: M_57.885.161 = 2^57.885.161 - 1. Este número, que tiene más de 17 millones de cifras es el primo más grande que se conoce por el momento, y ha sido hallado por  Curtis Cooper, profesor de la University of Central Missouri, aunque es  resultado es fruto de una iniciativa creada en 1996 bajo el proyecto GIMPS (Great Internet  Mersenne Prime Search), un programa de libre distribución en el que se puede participar libre y gratuitamente que ayuda a detectar grandes primos. Javier Cilleruelo y Juanjo Rué, investigadores del ICMAT, hablan de la búsqueda de primos al hilo de este acontecimiento.

Desde los tiempos de Euclides sabemos que la lista de los números primos es infinita. Su argumento, que aparece el  libro IX de su obra “Los elementos”, fue el siguiente: si p₁ , …, p_k fuese la lista completa de todos los primos, el número N= p₁  … p_k + 1 no sería divisible por ningunos de los primos de la lista y por lo tanto tendría que ser un nuevo primo.

Euclides, 325 – 265 a. C

No se conoce ninguna sucesión infinita “sencilla” que conste únicamente de números primos y comprobar si un número dado es primo requiere, en general, un algoritmo que es muy costoso en términos computacionales a medida que el tamaño del número aumenta. Estos algoritmos, que se conocen como tests de primalidad, son sin embargo mucho más eficientes para algunas familias de números.

Una de estas familias la constituyen  los números que son de la forma M_p= 2^p-1 con  p primo. Estos números, cuando son primos, se denominan primos de Mersenne. Los primeros números de esta lista son

M₂ = 3, M₃ = 7, M₅ = 31, M₇ = 127, M₁₃ = 8191, M₁₇ = 131071

El último primo descubierto hace unos días (25 de enero de 2013) también pertenece a esta familia:

M_57.885.161 = 2^57.885.161 - 1

Este número, que tiene más de 17 millones de cifras es el primo más grande que se conoce. El anterior, que tenía 12 millones de cifras también era un primo de Mersenne.

Marin Mersenne, 1588-1648

Los primos de Mersenne son además interesantes por su conexión con los números perfectos. Un número perfecto es aquel que es suma de sus divisores propios. Por ejemplo,

6=1+2+3   y   28= 1+2+4+7+14

son los dos primeros números perfectos. Euclides ya observó que todos los números de la forma 2^p-1(2^p-1) son números perfectos cuando M_p= 2^p-1 es primo. De hecho, todos los números perfectos pares son de esta forma.

Se cree que existen infinitos primos de Mersenne y en ese caso existirían infinitos números pares perfectos.

Pero los números perfectos impares siguen siendo un misterio: nadie ha encontrado ninguno pero tampoco se ha encontrado un argumento que demuestre que no existen.

El proyecto GIMPS.

Volviendo al hallazgo del último primo de Mersenne hasta el momento, ¿Quién ha encontrado este primo? ¿Cómo lo ha hecho?

Aunque la autoría se debe a Curtis Cooper, profesor de la University of Central Missouri, el resultado es fruto de una iniciativa creada en 1996 bajo el proyecto GIMPS (Great Internet  Mersenne Prime Search), un programa de libre distribución en el que se puede participar libre y gratuitamente instalando el programa que proporciona GIMPS. Lo que GIMPS hace es distribuir a cada usuario un intervalo para que el ordenador de cada uno compruebe si M_p  es primo para algún primo p del intervalo asignado. En realidad, para cada p, el ordenador comprueba primero si M_p  es divisible por algún primo pequeño. Eso va a ocurrir casi siempre. De no ser así, M_p pasa a ser un candidato a número primo y se procede a aplicar un test infalible denominado el test de Lucas-Lehmer.

El test consiste en calcular los elementos de la sucesión s₀ = 4, s_i = s²_i-1 – 2 para i  mayor o igual a 1,  y afirma que M_p  es primo si y sólo si s_p-2 es divisible por M_p .

Cooper ha recibido una recompensa de 3.000 $, que el proyecto GIMPS concede al afortunado descubridor de un nuevo record. Hay una recompensa de 50.000 $ para quien encuentre un primo con más de 100 millones de cifras, una manera muy digna de obtener un sobresueldo.

Entre los investigadores que usualmente visitan el ICMAT y el Departamento de Matemáticas de la UAM, se encuentra el profesor Pedro Berrizbeitia, de la universidad Simón Bolivar (Venezuela), que es una de las mayores autoridades en tests de primalidad. Pedro Berrizbeitia ha encontrado nuevos test de primalidad muy rápidos para familias más generales de números. En particular mejoró el famoso algoritmo AKS, que tiene un coste computacional de orden polinomial en el número de dígitos.

¿Qué utilidad tiene encontrar primos grandes?

El descubrimiento de este número primo no constituye un hito matemático de relevancia. No hay nada que ahora se entienda mejor que antes sobre los primos.  Pero cualquier matemático presumiría, con razón, de tener el honor de haber descubierto un número primo más grande mayor que todos los anteriores conocidos.

L. Euler 1707-1783

Entre los matemáticos notables que consiguieron el primo más grande en su momento figura L. Euler. En 1772 demostró que

2³¹ − 1 =2147483647

es un número primo. Este número fue el número primo más grande conocido hasta 1867.

Cabe comentar en estas líneas que la oficina postal de Urbana (Illinois)  utilizó un matasellos para celebrar el descubrimiento de un nuevo record obtenido por Donald B. Gillies en la universidad de Illinois.

Podría parecer por lo comentado anteriormente que el descubrimiento de primos grandes es simplemente un divertimento para satisfacer la vanidad de algunos matemáticos. Pero nada más lejos de la realidad. Además de las teorías matemáticas que ha impulsado, el conseguir fabricar muchos números primos grandes es una necesidad hoy en día. Los primos grandes se utilizan en los sistemas criptográficos y son los que nos permiten encriptar los mensajes, realizar transacciones comerciales con seguridad, etc.

————————-

Javier Cilleruelo (ICMAT-UAM) y Juanjo Rué (ICMAT)

Compartir