Gran búsqueda de Mersenne Prime en Internet

La Gran búsqueda de números primos de Mersenne en Internet (GIMPS) es un proyecto colaborativo de voluntarios que utilizan software disponible gratuitamente para buscar números primos de Mersenne.

GIMPS fue fundado en 1996 por George Woltman, quien también escribió el cliente Prime95 y su puerto Linux MPrime. Scott Kurowski escribió el servidor PrimeNet back-end para demostrar el software informático voluntario de Entropia, una empresa que fundó en 1997. GIMPS está registrado como Mersenne Research, Inc. con Kurowski como vicepresidente ejecutivo y director de la junta. Se dice que GIMPS es uno de los primeros proyectos informáticos voluntarios a gran escala a través de Internet con fines de investigación.

Hasta octubre de 2022, el proyecto ha encontrado un total de diecisiete números primos de Mersenne, quince de los cuales fueron el número primo más grande conocido en sus respectivos momentos de descubrimiento. El número primo más grande conocido hasta septiembre de 2022 es 2^{82 589 933} − 1 (o M_{82 589 933} para abreviar) y fue descubierto el 7 de diciembre de 2018 por Patrick Laroche. El 4 de diciembre de 2020, el proyecto superó un hito importante después de que todos los exponentes por debajo de 100 millones fueran verificados al menos una vez.

Desde su inicio hasta 2018, el proyecto se basó principalmente en la prueba de primalidad de Lucas-Lehmer, ya que es un algoritmo que está especializado para probar números primos de Mersenne y es particularmente eficiente en arquitecturas informáticas binarias. Antes de aplicarlo a un número de Mersenne dado, hubo una fase de división de prueba, utilizada para eliminar rápidamente muchos números de Mersenne con factores pequeños. El algoritmo p − 1 de Pollard también se usa para buscar factores suaves.

En 2018, GIMPS adoptó la prueba de primalidad de Fermat como una opción alternativa para las pruebas de primalidad, al tiempo que mantuvo la prueba de Lucas-Lehmer como una doble verificación de los números de Mersenne detectados como números primos probables por la prueba de Fermat. (Si bien la prueba de Lucas-Lehmer es determinista y la prueba de Fermat es solo probabilística, la probabilidad de que la prueba de Fermat encuentre un pseudoprimo de Fermat que no sea primo es mucho más baja que la tasa de error de la prueba de Lucas-Lehmer debido a errores de hardware de la computadora.)

En septiembre de 2020, GIMPS comenzó a admitir pruebas de primalidad basadas en funciones de retraso verificables. Los archivos de prueba se generan mientras la prueba de primalidad de Fermat está en curso. Estas pruebas, junto con un algoritmo de verificación de errores ideado por Robert Gerbicz, brindan una confianza total en la exactitud del resultado de la prueba y eliminan la necesidad de verificaciones dobles. Las pruebas de Lucas-Lehmer por primera vez quedaron obsoletas en abril de 2021.

GIMPS también tiene subproyectos para factorizar números compuestos de Mersenne y Fermat conocidos.

Historia

El proyecto comenzó a principios de enero de 1996, con un programa que se ejecutaba en computadoras i386. El nombre del proyecto fue acuñado por Luke Welsh, uno de sus primeros buscadores y co-descubridor del 29º primo de Mersenne. En unos pocos meses, varias docenas de personas se habían unido y más de mil al final del primer año. Joel Armengaud, un participante, descubrió la primalidad de M_1.398.269 el 13 de noviembre de 1996.

Estado

A partir de julio de 2022, GIMPS tiene un rendimiento agregado promedio sostenido de aproximadamente 4,71 petaFLOPS (o PFLOPS). En noviembre de 2012, GIMPS mantuvo 95 TFLOPS, lo que teóricamente le valió a la computadora virtual GIMPS el puesto 330 entre los TOP500 sistemas informáticos más poderosos del mundo. El lugar anterior lo ocupaba entonces un 'HP Cluster Platform 3000 BL460c G7' de Hewlett-Packard. A partir de los resultados TOP500 de julio de 2021, los números actuales de GIMPS ya no estarían en la lista.

Anteriormente, esto era aproximadamente 50 TFLOPS a principios de 2010, 30 TFLOPS a mediados de 2008, 20 TFLOPS a mediados de 2006 y 14 TFLOPS a principios de 2004.

Licencia de software

Aunque el código fuente del software GIMPS está disponible públicamente, técnicamente no es software libre, ya que tiene la restricción de que los usuarios deben cumplir con los términos de distribución del proyecto. Específicamente, si el software se usa para descubrir un número primo con al menos 100 000 000 de dígitos decimales, el usuario solo ganará $50 000 del premio de $150 000 que ofrece Electronic Frontier Foundation.

Los programas de terceros para probar los números de Mersenne, como Mlucas y Glucas (para sistemas que no son x86), no tienen esta restricción.

GIMPS también "se reserva el derecho de cambiar este EULA sin previo aviso y con un efecto retroactivo razonable."

Primos encontrados

Todos los números primos de Mersenne tienen la forma M_p = 2^p − 1, donde p es un número primo en sí mismo. El primo de Mersenne más pequeño de esta tabla es 2^1398269 − 1.

La primera columna es el rango del número primo de Mersenne en la secuencia (ordenada) de todos los números primos de Mersenne; GIMPS ha encontrado todos los números primos de Mersenne conocidos que comienzan con el 35.

^ † A partir del 11 de octubre de 2022, 61 809 281 es el exponente más grande por debajo del cual todos los demás exponentes primos se verificaron dos veces, por lo que no se verifica si existen números primos de Mersenne sin descubrir entre el 48 (M_57885161) y el 51 (M_82589933) en este gráfico; por lo tanto, la clasificación es provisional. Además, 110,194,351 es el exponente más grande por debajo del cual se han probado todos los demás exponentes primos al menos una vez, por lo que se han probado todos los números de Mersenne por debajo del 51 (M_82589933).

^ ‡ El número M_82589933 tiene 24 862 048 dígitos decimales. Para ayudar a visualizar el tamaño de este número, si se guardara en el disco, el archivo de texto resultante tendría casi 25 megabytes (la mayoría de los libros en formato de texto sin formato registran menos de dos megabytes). Un diseño de procesador de texto estándar (50 líneas por página, 75 dígitos por línea) requeriría 6629 páginas para mostrarlo. Si tuviera que imprimirlo utilizando papel de impresora estándar, a una cara, requeriría aproximadamente 14 resmas (14 × 500 = 7000 hojas) de papel.

Siempre que se informa al servidor de un posible primo, primero se verifica (mediante una o más pruebas independientes en diferentes máquinas) antes de anunciarse. La importancia de esto se ilustró en 2003, cuando se informó un falso positivo al servidor como un Mersenne prime pero la verificación falló.

La "fecha de descubrimiento" oficial de un primo es la fecha en que un ser humano notó por primera vez el resultado del primo, que puede diferir de la fecha en que el resultado se informó por primera vez al servidor. Por ejemplo, M_74207281 se informó al servidor el 17 de septiembre de 2015, pero el informe se pasó por alto hasta el 7 de enero de 2016.