Great Internet Mersenne Prime Search ( 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 back-end PrimeNet 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. [1]
Hasta octubre de 2022 [actualizar], el proyecto ha encontrado un total de diecisiete números primos de Mersenne, quince de los cuales eran el número primo más grande conocido en sus respectivos momentos de descubrimiento. El primo más grande conocido en septiembre de 2022 [árbitro]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. [2] El 4 de diciembre de 2020, el proyecto superó un hito importante después de que todos los exponentes inferiores a 100 millones fueran verificados al menos una vez. [3]
Desde su inicio hasta 2018, el proyecto se basó principalmente en la prueba de primalidad de Lucas-Lehmer [4], ya que es un algoritmo especializado para probar números primos de Mersenne y particularmente eficiente en arquitecturas de computadoras binarias . Antes de aplicarlo a un número de Mersenne determinado, 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 utiliza para buscar factores suaves .
En 2018, GIMPS adoptó una prueba de primalidad de Fermat como una opción alternativa para las pruebas de primalidad, [5] [ se necesita aclaración ] al tiempo que mantuvo la prueba de Lucas-Lehmer como una doble verificación de los números de Mersenne detectados como primos probables por la prueba de Fermat. [6] (Si bien la prueba de Lucas-Lehmer es determinista y la prueba de Fermat es sólo probabilística, la probabilidad de que la prueba de Fermat encuentre un pseudoprimo de Fermat que no sea primo es mucho menor que la tasa de error de la prueba de Lucas-Lehmer debido a errores informáticos) . errores de hardware . [7] )
En septiembre de 2020, [8] [9] [10] GIMPS comenzó a admitir pruebas de primalidad basadas en funciones de retraso verificables. [11] Los archivos de prueba se generan mientras se realiza la prueba de primalidad de Fermat. 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 realizar dobles verificaciones. Las primeras pruebas de Lucas-Lehmer quedaron obsoletas en abril de 2021. [12]
GIMPS también tiene subproyectos para factorizar números compuestos conocidos de Mersenne y Fermat . [13]
El proyecto comenzó a principios de enero de 1996, [14] [15] con un programa que se ejecutaba en computadoras i386 . [16] [17] El nombre del proyecto fue acuñado por Luke Welsh, uno de sus primeros buscadores y codescubridor del número 29 de Mersenne. [18] En unos pocos meses, se habían unido varias docenas de personas, y más de mil al final del primer año. [17] [19] Joel Armengaud, un participante, descubrió la primalidad de M 1.398.269 el 13 de noviembre de 1996. [20] Desde entonces, GIMPS ha descubierto un nuevo primo de Mersenne cada 1 o 2 años en promedio. Sin embargo, no se ha encontrado ningún nuevo primo de Mersenne desde 2018, lo que constituye el período más largo sin un nuevo descubrimiento desde el inicio del proyecto (más de 5 años a partir de 2024).
En julio de 2022 [actualizar], GIMPS tiene un rendimiento agregado promedio sostenido de aproximadamente 4,71 PetaFLOPS (o PFLOPS) . [21] En noviembre de 2012, GIMPS mantuvo 95 TFLOPS, [22] teóricamente le valió a la computadora virtual GIMPS un puesto 330 entre los 500 sistemas informáticos más potentes conocidos del mundo. [23] El puesto anterior lo ocupaba entonces una 'HP Cluster Platform 3000 BL460c G7' de Hewlett-Packard . [24] A partir de los resultados TOP500 de julio de 2021, los números actuales de GIMPS ya no figurarí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.
Aunque el código fuente del software GIMPS está disponible públicamente, [25] 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. [26] Específicamente, si el software se utiliza para descubrir un número primo con al menos 100.000.000 de dígitos decimales, el usuario sólo ganará 50.000 dólares del premio de 150.000 dólares ofrecido por la Electronic Frontier Foundation . (Por otro lado, ganará 3.000 dólares cuando descubrir un primo más pequeño que no califica para el premio.) [26] [27]
Los programas de terceros para probar números de Mersenne, como Mlucas [28] y Glucas [29] (para sistemas que no son x86), no tienen esta restricción.
GIMPS también "se reserva el derecho de cambiar este CLUF sin previo aviso y con efecto retroactivo razonable " . [26]
Todos los primos de Mersenne son de 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 en esta tabla es 2 1398269 − 1.
La primera columna es el rango del primo de Mersenne en la secuencia (ordenada) de todos los primos de Mersenne; [30] GIMPS ha encontrado todos los números primos de Mersenne conocidos a partir del día 35.
^ † A partir del 14 de noviembre de 2023 [actualizar], 65,723,341 es el exponente más grande por debajo del cual todos los demás exponentes primos se han verificado dos veces, por lo que no se verifica si existen primos de Mersenne no descubiertos entre el 48 (M 57885161 ) y el 51 (M 82589933 ). en este gráfico; Por tanto, la clasificación es provisional. Además, 114.055.847 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 ). [31]
^ ‡ 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 de largo (la mayoría de los libros en formato de texto plano pesan menos de dos megabytes). Un diseño de procesador de textos estándar (50 líneas por página, 75 dígitos por línea) requeriría 6.629 páginas para mostrarlo. Si se imprimiera utilizando papel de impresora estándar, a una cara, se necesitarían aproximadamente 14 resmas (14 × 500 = 7000 hojas) de papel.
Siempre que se informa al servidor de un posible cebado, primero se verifica (mediante una o más pruebas independientes en diferentes máquinas) antes de anunciarlo. La importancia de esto quedó ilustrada en 2003, cuando se informó al servidor de un falso positivo como Mersenne Prime, pero la verificación falló. [32]
La "fecha de descubrimiento" oficial de un Prime es la fecha en que un humano notó por primera vez el resultado del Prime, 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. [33]