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 fundada 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 de computación voluntaria de Entropia, una compañía que fundó en 1997. GIMPS está registrada como Mersenne Research, Inc. con Kurowski como vicepresidente ejecutivo y director de la junta. Se dice que GIMPS es uno de los primeros proyectos de computación voluntaria a gran escala a través de Internet con fines de investigación. [1]
Hasta octubre de 2024 [actualizar], el proyecto ha encontrado un total de dieciocho primos de Mersenne, dieciséis de los cuales fueron el mayor número primo conocido en sus respectivos momentos de descubrimiento. El mayor primo conocido hasta octubre de 2024 [árbitro]es 2 136 279 841 − 1 (o M 136 279 841 para abreviar) y fue descubierto el 12 de octubre de 2024 por Luke Durant. [2] [3] El 4 de diciembre de 2020, el proyecto alcanzó un hito importante después de que todos los exponentes por debajo de 100 millones se verificaran al menos una vez. [4]
Desde su inicio hasta 2018, el proyecto se basó principalmente en la prueba de primalidad de Lucas-Lehmer [5], ya que es un algoritmo especializado para probar primos de Mersenne y 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 utiliza para buscar factores suaves .
En 2018, GIMPS adoptó una prueba de primalidad de Fermat con base a = 3 [6] [7] como una opción alternativa para las pruebas de primalidad, [8] mientras que mantuvo la prueba de Lucas-Lehmer como una doble verificación para los números de Mersenne detectados como primos probables por la prueba de Fermat. [9] (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 menor que la tasa de error de la prueba de Lucas-Lehmer debido a errores de hardware de la computadora . [10] )
En septiembre de 2020, [11] [12] [13] GIMPS comenzó a admitir pruebas de primalidad basadas en funciones de retardo verificables. [14] 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 comprobaciones dobles. Las pruebas Lucas-Lehmer realizadas por primera vez quedaron obsoletas en abril de 2021. [15]
GIMPS también tiene subproyectos para factorizar números compuestos conocidos de Mersenne y Fermat . [16]
El proyecto comenzó a principios de enero de 1996, [17] [18] con un programa que se ejecutaba en computadoras i386 . [19] [20] El nombre del proyecto fue acuñado por Luke Welsh, uno de sus primeros investigadores y codescubridor del 29.º primo de Mersenne. [21] En pocos meses, varias docenas de personas se habían unido, y más de mil al final del primer año. [20] [22] Joel Armengaud, un participante, descubrió la primalidad de M 1.398.269 el 13 de noviembre de 1996. [23] Desde entonces, GIMPS ha descubierto un nuevo primo de Mersenne cada 1 o 2 años en promedio. Sin embargo, el primo más grande más reciente encontrado en octubre de 2024 tardó casi seis años en encontrarse.
A partir de julio de 2022 , GIMPS tiene un rendimiento[actualizar] agregado promedio sostenido de aproximadamente 4,71 PetaFLOPS (o PFLOPS) . [24] En noviembre de 2012, GIMPS mantuvo 95 TFLOPS, [25] lo que teóricamente le valió al ordenador virtual GIMPS un puesto 330 entre los TOP500 sistemas informáticos conocidos más potentes del mundo. [26] El lugar anterior lo ocupaba entonces un 'HP Cluster Platform 3000 BL460c G7' de Hewlett-Packard . [27] A partir de los resultados TOP500 de julio de 2021, los números actuales de GIMPS ya no aparecerí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, [28] técnicamente no es software libre , ya que tiene una restricción de que los usuarios deben cumplir con los términos de distribución del proyecto. [29] En concreto, 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 si descubre un primo más pequeño que no califique para el premio. [29] [30]
Los programas de terceros para probar números de Mersenne, como Mlucas [31] y Glucas [32] (para sistemas que no sean x86), no tienen esta restricción.
GIMPS también "se reserva el derecho de cambiar este EULA sin previo aviso y con efecto retroactivo razonable " . [29]
Todos los primos de Mersenne tienen la forma M p = 2 p − 1 , donde p es un número primo. El primo de Mersenne más pequeño de 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; [33] GIMPS ha encontrado todos los primos de Mersenne conocidos comenzando con el 35.
^ † Al 14 de noviembre de 2023 [actualizar], 65.723.341 es el exponente más grande por debajo del cual se han comprobado dos veces todos los demás exponentes primos, por lo que no se ha verificado 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 comprobado todos los demás exponentes primos al menos una vez, por lo que se han comprobado todos los números de Mersenne por debajo del 51.º (M 82589933 ). [34]
^ ‡ El número M 136279841 tiene 41.024.320 dígitos decimales. Para ayudar a visualizar el tamaño de este número, si se guardara en un disco, el archivo de texto resultante tendría una longitud de casi 42 megabytes (la mayoría de los libros en formato de texto simple tienen menos de dos megabytes). Un diseño estándar de procesador de texto (50 líneas por página, 75 dígitos por línea) requeriría 10.940 páginas para mostrarlo. Si uno lo imprimiera usando papel de impresora estándar, por una sola cara, necesitaría aproximadamente 22 resmas (22 × 500 = 11000 hojas) de papel.
Cada vez que se informa al servidor de un posible primo, se verifica primero (mediante una o más pruebas independientes en diferentes máquinas) antes de anunciarlo. La importancia de esto quedó demostrada en 2003, cuando se informó al servidor de un falso positivo como primo de Mersenne, pero la verificación falló. [35]
La "fecha de descubrimiento" oficial de un número primo es la fecha en la que un ser humano notó por primera vez el resultado del número primo, que puede ser distinta de la fecha en la que el resultado se informó por primera vez al servidor. Por ejemplo, el número 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. [36]