Cómo construir un gran número primo | Revista Cuanta

Los números primos son cosas complicadas. Aprendemos en la escuela que son números sin más factores que 1 y ellos mismos, y que los matemáticos saben desde hace miles de años que existe un número infinito de ellos. Producir uno a pedido no parece que sea difícil.

Pero es. La construcción de números primos arbitrariamente grandes es notablemente complicada. Básicamente tiene dos opciones computacionales, ambas con inconvenientes. Podría usar la aleatoriedad y encontrar uno adivinando, pero el método es inconsistente: corre el riesgo de generar un número primo diferente cada vez. O podría usar un algoritmo determinista más confiable, pero con un alto costo computacional.

En mayo, un equipo de informáticos mostró que un tipo de enfoque híbrido también podría funcionar. Publicaron un algoritmo que combina efectivamente los enfoques aleatorio y determinista para generar un número primo de una longitud específica, con una alta probabilidad de generar el mismo, incluso si el algoritmo se ejecuta muchas veces. El algoritmo conecta la aleatoriedad y la complejidad de formas interesantes, y también podría ser útil para la criptografía, donde algunos esquemas de codificación se basan en la construcción de grandes números primos.

"Presentaron una secuencia de intentos, cada uno de ellos tratando de construir un número primo de una longitud diferente, y demostraron que uno de los intentos funciona", dijo. Roei Tell, un informático teórico del Instituto de Estudios Avanzados que no participó en el trabajo. “Es una construcción que genera un primo elegido de manera determinista, pero te permite lanzar monedas y tomar decisiones aleatorias en el proceso”.

El desafío de hacer una receta eficiente para números primos tiene raíces profundas. “Realmente no sabemos mucho sobre cómo se distribuyen los números primos o sobre los espacios en los números primos”, dijo Ofer Grossman, que estudia algoritmos pseudoaleatorios. Y si no sabemos dónde encontrarlos, no hay una manera fácil de generar un número primo desde cero.

Con el tiempo, los investigadores desarrollaron los enfoques antes mencionados. La forma más sencilla es simplemente adivinar. Si desea un número primo con 1,000 dígitos, por ejemplo, puede elegir un número de 1,000 dígitos al azar y luego verificarlo. “Si no es primo, prueba con otro, y otro, y así sucesivamente hasta encontrar uno”, dijo. Raúl Santhanam, científico informático de la Universidad de Oxford y coautor del nuevo artículo. "Debido a que hay muchos números primos, este algoritmo le dará un número que es primo con una alta probabilidad, después de un número relativamente pequeño de iteraciones". Pero usar la aleatoriedad significa que probablemente obtendrás un número diferente cada vez, dijo. Eso podría ser un problema si necesita consistencia, si, por ejemplo, está empleando un método criptográfico de seguridad que depende de la disponibilidad de números primos grandes.

El otro enfoque es ir con un algoritmo determinista. Puede elegir un punto de partida y comenzar a probar números, secuencialmente, para primalidad. Eventualmente, está destinado a encontrar uno, y su algoritmo generará consistentemente el primero que encuentre. Pero podría tomar un tiempo: si está buscando un número primo con 1,000 dígitos, incluso un cálculo con 2⁵⁰⁰ pasos, que tomarían mucho más tiempo que la edad del universo, no es suficiente para garantizar el éxito.

En 2009, el matemático y medallista de Fields Terence Tao quería hacerlo mejor. Retó a los matemáticos a idear un algoritmo determinista para encontrar un número primo de un tamaño dado dentro de un límite de tiempo computacional.

Ese límite de tiempo se conoce como tiempo polinomial. Un algoritmo resuelve un problema en tiempo polinomial si el número de pasos que da no es más que una función polinomial de n, el tamaño de la entrada. (Una función polinómica incluye términos que tienen variables elevadas a potencias enteras positivas, como n² o 4n³.) En el contexto de la construcción de números primos, n se refiere al número de dígitos en el número primo que desea. Computacionalmente hablando, esto no cuesta mucho: los informáticos describen problemas que pueden resolverse mediante algoritmos en tiempo polinomial como fáciles. Un problema difícil, por el contrario, toma un tiempo exponencial, lo que significa que requiere una cantidad de pasos aproximados por una función exponencial (que incluye términos como 2ⁿ).

Durante décadas, los investigadores han investigado la conexión entre la aleatoriedad y la dureza. El problema de construcción de números primos se consideraba fácil si permitía la aleatoriedad y se contentaba con recibir un número diferente cada vez, y difícil si insistía en el determinismo.

Nadie ha logrado superar el desafío de Tao todavía, pero el nuevo trabajo se acerca. Se basa en gran medida en un enfoque introducido en 2011 por Shafi Goldwasser y Eran Gat, científicos informáticos del Instituto Tecnológico de Massachusetts. Describieron algoritmos "pseudodeterministas": recetas matemáticas para problemas de búsqueda, como encontrar grandes números primos, que podrían aprovechar los beneficios de la aleatoriedad y, con una alta probabilidad, aún producir la misma respuesta cada vez. Usarían la eficiencia de los bits aleatorios en la receta, que serían des-aleatorizados en el resultado, pareciendo deterministas.

Los investigadores han estado explorando algoritmos pseudodeterministas desde entonces. En 2017, Santhanam e Igor Oliveira de la Universidad de Warwick (quien también contribuyó al nuevo trabajo) descrito un enfoque pseudodeterminista para construir números primos que utilizaba la aleatoriedad y parecía convincentemente determinista, pero funcionaba en un tiempo "subexponencial", más rápido que el exponencial, pero más lento que el tiempo polinomial. Luego, en 2021, Tell and lijie chen, científico informático de la Universidad de California, Berkeley, explorado cómo usar un problema difícil para construir un generador de números pseudoaleatorios (un algoritmo que genera una cadena de números indistinguibles de una salida aleatoria). “[Nosotros] encontramos una nueva conexión entre la dureza y la pseudoaleatoriedad”, dijo Chen.

Las piezas finalmente se juntaron en la primavera de 2023, durante un bootcamp sobre complejidad computacional en el Instituto Simons para la Teoría de la Computación en Berkeley, cuando los investigadores comenzaron a trabajar juntos en el problema, entretejiendo resultados anteriores. Para el nuevo trabajo, dijo Chen, Hanlin Ren, científico informático de Oxford y coautor, tuvo las ideas iniciales para combinar el resultado de Chen-Tell con el enfoque de Santhanam-Oliveira de una manera novedosa. Luego, todo el equipo desarrolló las ideas de manera más completa para producir el nuevo documento.

El algoritmo pseudodeterminista resultante, dijo Santhanam, utilizó nuevas formas de ver el trabajo anterior para producir números primos en tiempo polinomial. Probablemente usó la aleatoriedad para generar un número primo de una longitud específica, y la herramienta es más precisa que las conjeturas aleatorias y más eficiente computacionalmente que el análisis determinista.

El nuevo algoritmo también es notablemente simple, dijo Santhanam, y se puede aplicar a una amplia gama de problemas de búsqueda; en realidad, a cualquier subconjunto denso de números, como los números primos, para los cuales la pertenencia se puede determinar en tiempo polinomial. Pero no es perfecto. El algoritmo funciona para una cantidad infinita de longitudes de entrada, pero no cubre todas las longitudes de dígitos. Todavía puede haber algunos valores de n por ahí para el cual el algoritmo no produce deterministamente un número primo.

“Sería genial deshacerse de esa pequeña advertencia”, dijo Grossman.

El objetivo final, dijo Santhanam, es encontrar un algoritmo que no requiera aleatoriedad en absoluto. Pero esa búsqueda permanece abierta. “El determinismo es lo que nos gustaría usar”, dijo.

Pero también señaló que los procesos pseudoaleatorios son herramientas poderosas, y proyectos como la construcción de números primos son solo una forma de usarlos para conectar ideas de matemáticas, informática, teoría de la información y otras áreas.

“Es emocionante tratar de pensar a dónde más conducirán estas brillantes observaciones”, dijo Tell.