En agosto de 2008, se descubrió un nuevo número primo de Mersenne en uno de los ordenadores del Programa de Informática (PIC) del Departamento de Matemáticas de la UCLA. Este número resulta ser el mayor número primo conocido del mundo, y el descubrimiento ha generado mucho interés. En un esfuerzo por ahorrar tiempo y energía a todo el mundo, he pensado en colgar en la web información en formato de preguntas frecuentes.
Dado que muchas de las preguntas que he recibido proceden de personas sin formación técnica (incluidos niños), estas FAQ no son técnicas. Eso sí, hay que saber qué es un número primo.
No obstante, me veo obligado a hacer esta advertencia: aunque trabajo para el Departamento de Matemáticas, soy administrador de sistemas, no matemático. Si busca información seria sobre los números primos de Mersenne, le remito al excelente sitio web de Chris Caldwell Mersenne Primes: Historia, teoremas y listas. Otros sitios interesantes son la página de Wolfram Mersenne Prime y el entretenido Mersenne Prime Digits and Names de Landon Curt Noll.
Y ahora, ¡las preguntas!
Q. ¿Qué es un primo Mersenne?
A. En resumen, hay una subclase de números primos conocidos como primos de Mersenne. Deben su nombre a Marin Mersenne, un matemático del siglo XVII. En el momento de escribir este artículo, hay menos de 50 números primos de Mersenne conocidos.
Todos los números primos de Mersenne tienen la forma 2P-1, donde P es un primo conocido. El primer primo de Mersenne es 3 porque 22 -1 = 3. Observe que el exponente P es un número primo, en este caso 2. El siguiente primo Mersenne es 7 porque 23 - 1 = 7, siendo P el número primo 3. A continuación viene 31 (25 - 1), luego 127 (27 - 1), 8191 (213 - 1) y 131071 (217 - 1).
Como puede ver, después de los primeros, los números primos de Mersenne se hacen grandes muy rápidamente. Hay una buena tabla de los números primos de Mersenne conocidos aquí que le dará algo de perspectiva.
Los más pequeños de estos números eran conocidos en la antigüedad, pero hasta 1951 sólo 12 habían sido descubiertos. En los últimos 50 años, se han descubierto varias docenas más con la ayuda de ordenadores. Los números primos de Mersenne descubiertos más recientemente son asombrosamente grandes, con millones de dígitos. El primo Mersenne de la UCLA tiene unos 12,9 millones de dígitos.
Tenga en cuenta que todos los números primos de Mersenne son números primos, pero muy pocos números primos son números primos de Mersenne.
Q. ¿Qué es el primo de Mersenne de la UCLA? ¿Por qué es especial?
A. El primo de Mersenne de la UCLA es el primer número primo descubierto que tiene más de 10 millones de dígitos. Se descubrió en el departamento de Matemáticas de la UCLA el 23 de agosto de 2008.
Todos los números primos de Mersenne son especiales por su rareza, pero éste ha recibido una atención especial porque puede optar a un premio (véase más abajo).
El número primo de Mersenne de la UCLA es 243112609 - 1. El número real tiene 12.978.189 dígitos. Si le interesa, Landon Curt Noll, investigador de números primos de Mersenne desde hace mucho tiempo, ha puesto el número a su disposición aquí. Si le interesa mucho, también puede consultar el número completo en inglés (los 328 megabytes que contiene) aquí.
Q. ¿Es éste el primer número Mersenne de UCLA?
A. En realidad, ¡es el octavo número primo Mersenne de la UCLA!
En 1952, el profesor Raphael Robinson encontró 5 nuevos números primos de Mersenne utilizando el Standards Western Automatic Computer (SWAC) de la UCLA, uno de los ordenadores más rápidos de su época. Se trataba de los números 13 a 17 descubiertos y cada uno de ellos tenía cientos de dígitos. Los números primos de Mersenne de Robinson fueron los primeros que se descubrieron en 75 años y los primeros que se descubrieron utilizando un ordenador digital.
En 1961, el matemático de la UCLA Alexander Hurwitz descubrió los números 19 y 20 de los Primeros de Mersenne en el ordenador central IBM 7090 del Centro de Computación de la UCLA. Cada uno de estos números tenía más de 1.200 dígitos.
Ahora, 47 años después, la tradición de la UCLA de descubrir los primos de Mersenne continúa.
Q. ¿Quién busca los primos de Mersenne? ¿Cómo lo hacen?
A. Miles de personas utilizando decenas de miles de ordenadores están participando en la Gran Búsqueda de Primeros Mersenne en Internet (GIMPS), un esfuerzo organizado dedicado a la búsqueda de Primeros Mersenne. Este es uno de los muchos esfuerzos en curso en el campo de la computación distribuida, y podría decirse que el más exitoso.
La búsqueda está muy bien organizada. La buena gente de Primenet ha estado coordinando el esfuerzo durante los últimos 12 años, y proporciona el excelente programa Prime95 de forma gratuita a cualquiera que quiera ejecutarlo. Llevan un registro de los números que han sido probados y proporcionan un flujo constante de números candidatos no probados a la comunidad del GIMPS. Los participantes en el GIMPS se clasifican en función de su productividad. Puedes encontrarnos bajo el nombre de UCLA_Math; normalmente estamos clasificados en algún lugar entre el puesto 40 y el 55.
Una sola máquina puede tardar meses en probar un solo número candidato, pero si se aprovecha la potencia de los ordenadores individuales conectados a Internet en todo el mundo, se puede avanzar rápidamente.
Q. ¿Cuáles son las probabilidades de descubrir un primo de Mersenne?
A. Según el proyecto GIMPS, la probabilidad de que cualquier número candidato resulte ser un primo de Mersenne es de 1 entre 150.000.
Q. ¿Cómo se comprueban los números para ver si son primos de Mersenne?
A. Hay muchos números de la forma 2P- 1, pero sólo unos pocos de ellos son primos de Mersenne. Hay una serie de técnicas para probar estos números para ver si son primos de Mersenne, pero el método inicial es tratar de factorizar el exponente candidato, P, y luego tratar de factorizar el primo candidato, 2P-1, utilizando algunos primos pequeños.
Hay un algoritmo de 75 años de antigüedad llamado Prueba Lucas-Lehmer que es ampliamente reconocido como la mejor herramienta para probar Primas Mersenne. El programa Prime95 utiliza ampliamente este método, así como algunos otros. Una explicación va más allá del alcance de este documento, pero el lector interesado puede obtener más información aquí.
Q. ¿Por qué busca la gente los primos Mersenne? ¿Para qué sirven?
A. Por las mismas razones que la gente escala montañas, navega por mares desconocidos y explora el cosmos. Es un reto. Es emocionante superar los límites de las matemáticas computacionales y buscar algo desconocido que crees que está ahí fuera. Además, a diferencia de los antiguos exploradores, nosotros podemos sentarnos en cómodas sillas de oficina mientras buscamos.
Esto no quiere decir que los números primos de Mersenne no tengan valor matemático. Sin duda son valiosos en el campo de la criptografía y pueden tener otros usos aún por descubrir.
El investigador de números primos Chris Caldwell profundiza en esta cuestión en su artículo "¿Por qué la gente encuentra estos números primos?".
Q. Aparte del reto, ¿por qué decidió participar?
A. Como ha ocurrido en muchos otros sitios, nos dimos cuenta de que nuestro gran laboratorio informático PIC/Math (75 puestos) sólo utilizaba una fracción de la potencia de CPU disponible. En lugar de desperdiciar todos esos ciclos, estudiamos varios proyectos de computación distribuida y decidimos que GIMPS era el más adecuado para nosotros. Además de la idoneidad de que GIMPS fuera un proyecto basado en Matemáticas, encontramos que estaba muy bien escrito y no interfería con los usuarios de ordenadores de pregrado (esto no era cierto de algunos de los otros proyectos de software que investigamos).
El Programa de Informática (PIC) atrae a estudiantes de todo el campus, por lo que era importante para nosotros que cualquier proyecto informático del laboratorio fuera comprensible para todos. GIMPS encajaba a la perfección en este caso y, además, pensamos que la competición informal entre los centros GIMPS sería interesante para nuestros estudiantes y aumentaría su conocimiento de las Matemáticas Computacionales.
Q. ¿Qué hicieron para organizarlo? ¿Fue complicado?
A. El software GIMPS Prime95 es muy sencillo desde el punto de vista de la administración del sistema. Es fácil de instalar y no requiere mantenimiento.
El software Prime95 envía actualizaciones periódicas sobre su estado de procesamiento a los ordenadores centrales de Primenet. Si el equipo en el que se ejecuta se cae, los cálculos se reanudarán donde se quedaron cuando el equipo vuelva a funcionar. Si una caja individual está fuera de servicio durante un período prolongado, Primenet recuperará el número y lo asignará a otra persona, y asignará un nuevo número cuando la máquina vuelva a estar en servicio.
Q. ¿Cómo funciona la verificación?
A. Cuando se encuentra un número primo de Mersenne, no se hace un anuncio formal hasta que una tercera parte independiente valida la afirmación. Con números excepcionalmente grandes como éstos, siempre hay una pequeña posibilidad de que se produzca un problema computacional con el algoritmo utilizado, o con la CPU del propio ordenador (el Problema del punto flotante de Intel es un ejemplo clásico de esto).
Debido a estos problemas potenciales, los Primeros Mersenne son siempre validados usando un algoritmo completamente diferente en un ordenador con una arquitectura diferente. La verificación puede llevar dos semanas o más.
Q. ¿Cuándo se produjo el descubrimiento? ¿Qué tipo de ordenador se utilizó?
A. El cebador Mersenne de la UCLA se descubrió el 23 de agosto de 2008 en un ordenador llamado zeppelin.pic.ucla.edu, un Dell Optiplex 745 con Windows XP y una CPU Intel Core 2 Duo E6600 a 2,4 GHz. El nombre "zeppelin" formaba parte de nuestra serie de ordenadores Classic Rock Band.
Q. ¿Qué es eso de los premios en metálico?
A. La Electronic Frontier Foundation (EFF), la principal organización de defensa de las libertades civiles en Internet, patrocina los Cooperative Computing Awards. Estos premios pretenden "animar a los usuarios de Internet a contribuir a la resolución de grandes problemas científicos" y están dotados con premios en metálico cuando se alcanzan determinados objetivos.
La EFF tiene un premio permanente de 100.000 dólares para el primer número primo de 10 millones de dígitos que se descubra. El primo Mersenne de la UCLA tiene casi 12,9 millones de dígitos y cumple los criterios del premio. Una vez publicados los resultados formales en una revista adecuada, se concederá el premio. Esto ocurrirá como muy pronto en 2009.
Por acuerdo previo, sólo el 50% del premio se destinará al descubridor del primo de 10 millones de dígitos. El 25% se destinará a obras benéficas y, en reconocimiento de la naturaleza colaborativa del GIMPS, la mayor parte del 25% restante irá a los descubridores de otros primos de Mersenne, con una pequeña cantidad para el propio GIMPS.
Q. ¿Qué es eso que he oído sobre un póster? ¿Habrá uno para el primo Mersenne de UCLA?
A. Durante años, una empresa llamada Perfectly Scientific ha estado creando un póster del mayor número primo explícito conocido en la actualidad. El póster de M44, producido en 2006, utilizaba un tipo de letra extremadamente pequeño para comprimir 9,8 millones de dígitos en un único póster de 29 por 40 pulgadas. La empresa ofrecía una lupa de joyero junto con el póster para que pudiera leerse.
Richard Crandall, de Perfectly Scientific, se puso en contacto conmigo hace poco para informarme de que ya se puede comprar el póster de Mersenne Prime de la UCLA. Cuesta 99 dólares, sin marco, y está disponible en el sitio web de Perfectly Scientific.
Q. ¿Qué pasa con el otro Mersenne Prime descubierto recientemente?
A. Dos semanas después de que se descubriera el primo Mersenne de la UCLA, otro primo Mersenne de más de 10 millones de dígitos fue descubierto por Hans-Michael Elvenich en Alemania. Con 11,2 millones de dígitos, es aproximadamente un 10% más pequeño que el primo Mersenne de la UCLA.
No es la primera vez que se descubren primos de Mersenne fuera de orden. En 1988, Colquitt y Welsh descubrieron un primo de Mersenne más pequeño que los dos anteriores, descubiertos en 1983 y 1985.
En el momento de escribir este artículo, el primo de Mersenne de la UCLA se considera el 46º primo de Mersenne (llamado "M46" por la comunidad que busca primos de Mersenne), aunque fue el 45º descubierto. El primo Mersenne de Elvenich es M45, ¡pero fue el 46 descubierto!
Como complicación adicional, no todos los primos potenciales entre M39 (descubierto en 2001) y el primo Mersenne de la UCLA han sido probados, por lo que podría haber más encontrados en ese rango en una fecha futura. Si es así, el primo de la UCLA será "ascendido" a M47.
Mi más sincero agradecimiento a todas las personas que me han ayudado con este documento. Gracias a Sal Zapien y Mary Margaret Smith por su excelente corrección de pruebas, y a Jim Carter por su ayuda con la estructura y la organización. En especial, quiero dar las gracias a Robert Johnson, que se aseguró de que todas y cada una de mis afirmaciones se ajustaban a la realidad y corrigió amablemente mis numerosos conceptos erróneos.
Este FAQ creado y mantenido por Edson Smith. Última actualización julio, 2018.
Original article: www.math.ucla.edu/~edson/prime/