Hace unos días se ha descubierto último primo de Mersenne: M57.885.161 = 257.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 p1 , …, pk fuese la lista completa de todos los primos, el número N= p1 … pk + 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 Mp= 2p-1 con p primo. Estos números, cuando son primos, se denominan primos de Mersenne. Los primeros números de esta lista son
M2 = 3, M3 = 7, M5 = 31, M7 = 127, M13 = 8191, M17 = 131071
El último primo descubierto hace unos días (25 de enero de 2013) también pertenece a esta familia:
M57.885.161 = 257.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 2p-1(2p-1) son números perfectos cuando Mp= 2p-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 Mp es primo para algún primo p del intervalo asignado. En realidad, para cada p, el ordenador comprueba primero si Mp es divisible por algún primo pequeño. Eso va a ocurrir casi siempre. De no ser así, Mp 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 s0 = 4, si = s2i-1 – 2 para i mayor o igual a 1, y afirma que Mp es primo si y sólo si sp-2 es divisible por Mp .
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
231 − 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)