El matemático griego Euclides pudo haber demostrado, alrededor del año 300 a. C., que hay infinitos números primos. Pero fue el matemático británico Christian Lawson-Perfect quien, más recientemente, ideó el videojuego Is this prime? (¿Es este un número primo?)

Lanzado hace cinco años, el videojuego superó los tres millones de intentos el 16 de julio o, más concretamente, alcanzó 2.999.999, después de que un artículo en de Hacker News provocara un aumento de aproximadamente 100.000 intentos.

El objetivo consiste en clasificar tantos números como sea posible en "primo" o "no primo" en 60 segundos (como Lawson-Perfect lo describió originalmente en The Aperiodica l, el blog de matemáticas del que es fundador y editor). Un número primo es un número entero con solo dos divisores, 1 y él mismo. "Es muy simple, pero exasperantemente difícil", reconoce Lawson-Perfect, que trabaja en la Unidad de Aprendizaje Electrónico de la Escuela de Matemáticas y Estadística de la Universidad de Newcastle (Reino Unido).

Creó el videojuego en su tiempo libre, pero le resultó útil en su trabajo porque escribe software de evaluación electrónica (sistemas que evalúan el aprendizaje). El creador detalla: "El sistema que yo hago está diseñado para generar aleatoriamente una pregunta matemática y recibir una respuesta del estudiante, que automáticamente se marca y se da el resultado. El juego de los números primos se podría ver como una especie de evaluación", y lo utilizó cuando realizaba sesiones de divulgación en las escuelas.

Lawson-Perfect hizo que el juego fuera un poco más fácil con atajos de teclado (las teclas y y n hacen clic en los botones correspondientes de sí-no en la pantalla) para ahorrar tiempo de movimiento del ratón. Y, ahora, a probarlo.

Algoritmos de prueba de primalidad

Los números primos tienen una utilidad práctica en informática, como con los códigos de corrección de errores y con el cifrado. Pero mientras que la factorización primaria es difícil (de ahí su valor en el cifrado), la prueba de la primalidad es más fácil, aunque complicada. El matemático alemán ganador de la medalla Fields Alexander Grothendieck confundió infamemente el 57 con un número primo (el "primo de Grothendieck"). Cuando Lawson-Perfect analizó los datos de su videojuego, descubrió que varios números mostraban un cierto tipo de error al estilo de "Grothendieck". El número que se confunde con mayor frecuencia con un número primo fue 51, seguido de 57, 87, 91, 119 y 133, la némesis de Lawson-Perfect (también ideó un útil servicio de prueba de primalidad: https://isthisprime.com/2).

El algoritmo más minimalista para verificar la primacía de un número es la división de prueba: divida el número por cada número hasta su raíz cuadrada (el resultado de dos números mayores que la raíz cuadrada sería mayor que el número en cuestión).

Sin embargo, este simple método no es muy eficiente, y tampoco algunas otras técnicas ideadas a lo largo de los siglos; como observó el matemático alemán Carl Friedrich Gauss en 1801, "requieren un trabajo intolerable incluso para el calculador más infatigable".

El algoritmo que Lawson-Perfect programó para el videojuego se llama prueba de primalidad de Miller-Rabin (que se basa en un método muy eficiente, pero no infalible del siglo XVII, el "pequeño teorema de Fermat"). La prueba de Miller-Rabin funciona sorprendentemente bien. En lo que respecta a Lawson-Perfect, es "básicamente mágico", y afirma: "No entiendo realmente cómo funciona, pero estoy seguro de que podría hacerlo si dedicara el tiempo a analizarlo más profundamente".

Dado que la prueba utiliza la aleatoriedad, produce un resultado probabilístico. Lo que significa que a veces miente. "Existe la posibilidad de descubrir un impostor, un número compuesto que intenta pasar como primo", resalta el matemático del Dartmouth College (EE. UU.) y coautor del libro Prime Numbers: A Computational Perspective, Carl Pomerance. Sin embargo, las posibilidades de que un impostor se cuele a través del inteligente mecanismo de verificación del algoritmo son quizás una en un billón, por lo que la prueba resulta "bastante segura".

Pero, en lo que respecta a los algoritmos inteligentes de verificación de la primalidad, la prueba de Miller-Rabin es "la punta del iceberg", según Pomerance. En efecto, hace 19 años, tres científicos informáticos del Instituto Indio de Tecnología de Kanpur (la India), Manindra Agrawal, Neeraj Kayal y Nitin Saxena, presentaron la prueba de primalidad AKS (de nuevo basada en el método de Fermat), que finalmente proporcionó una prueba para demostrar de manera inequívoca que un número es primo, sin aleatorización y (teóricamente, al menos) a una velocidad impresionante. Lamentablemente, lo rápido en teoría no siempre se traduce en la misma rapidez en la vida real, por lo que la prueba AKS no es útil para los fines prácticos.

El récord mundial no oficial

Pero lo práctico no siempre es lo más importante. De vez en cuando, Lawson-Perfect recibe correos electrónicos de personas interesadas en compartir sus puntuaciones más altas en el videojuego. Recientemente, un jugador logró 60 primos en 60 segundos, pero el récord más probable es el de 127 (Lawson-Perfect no registra las puntuaciones altas; sabe que hay tramposos, con intentos asistidos por ordenador que producen picos en los datos).

La puntuación de 127 fue lograda por el estudiante de matemáticas en la Universidad de California en Berkeley (EE. UU.) Ravi Fernando, quien publicó su resultado en julio de 2020. Sigue siendo su mejor marca personal y, según él, el "récord mundial no oficial".

Desde el verano pasado, Fernando no ha jugado mucho con la configuración predeterminada, sino con las personalizadas, con números más grandes y límites de tiempo más largos: acertó 240 con un límite de cinco minutos. El joven admite: "Requirió muchas conjeturas, porque los números entraron en el rango alto de cuatro dígitos y solo he memorizado los números primos por debajo de 3.000. Supongo que algunos dirían que incluso eso es excesivo".

La investigación de Fernando es sobre la geometría algebraica, que involucra los números primos hasta cierto punto. Pero, él mismo explica que "la investigación tiene más que ver con por qué dejé de jugar que por qué empecé" (comenzó su doctorado en 2014). Además, Fernando cree que 127 sería muy difícil de superar. Y, concluye: "Simplemente parece correcto parar dejar un récord que en sí mismo es un número primo".