La dificultad de generar primos de 1024 bits

• Introducción
  • Los números primos se pueden explicar fácilmente, pero encierran una enorme complejidad.
  • Se usan en conceptos matemáticos, visualizaciones interesantes, criptografía y muchas otras áreas.
  • Se decidió intentar generar primos mediante programación.
• Reto
  • Generar números primos que puedan usarse en el algoritmo RSA
  • Como la longitud adecuada para una clave RSA actual es de 2048 bits, se necesitan dos primos de 1024 bits
  • Restricciones:
    • Escribir código desde cero (sin dependencias externas)
    • Usar solo una CPU AMD Ryzen 7 y 16 GB de RAM de portátil
    • Generar primos en un tiempo "razonable"
  • Elección del lenguaje Rust
• Generación de primos de 16 bits
  • Generar números aleatorios usando el generador pseudoaleatorio /dev/urandom
  • Usar división por ensayo (Trial Division), un método simple de prueba de primalidad
  • Es posible generar un primo de 16 bits en unos 40 ms de promedio
• Generación de primos de 64 bits
  • Implementar un algoritmo de división por ensayo optimizado
    • Verificar solo números con forma 6k±1
    • Generar una lista de primos pequeños primero para filtrar antes los números fácilmente divisibles
  • Tras la optimización, se tardó aproximadamente 6 segundos
  • Para números más grandes, hay límites al usar algoritmos deterministas
• Pruebas de primalidad probabilísticas
  • Uso del Pequeño Teorema de Fermat (Fermat's Little Theorem)
    • Existe el problema de que también los compuestos pueden cumplir la condición (pseudoprimos)
  • Prueba de Miller-Rabin (Miller-Rabin Primality Test)
    • Prueba probabilística que mejora la prueba de Fermat
    • No existe un número compuesto que sea pseudoprimo para una base determinada en todos los casos
    • La probabilidad de error es muy baja y su uso es práctico
• Generación de primos de 128 bits
  • Puede generarse rápidamente con la prueba de Miller-Rabin (promedio 0.03 s)
  • Es difícil escalar a 1024 bits por la limitación del tipo u128
• Implementación de BigInt para 1024 bits
  • Mejoras progresivas tras múltiples intentos
    • Intento 1: guardar cada dígito del número en un arreglo
    • Intento 2: guardar el número en representación binaria
    • Intento 3: guardar el número en bloques de bytes
    • Intento 4: guardar el número en bloques de u64
    • Intento 5: optimizar los algoritmos de operaciones básicas
  • Optimización de la prueba de Miller-Rabin y de la lógica completa
  • Procesamiento paralelo con multithreading
• Resultado final
  • Posible generar un primo de 1024 bits en alrededor de 40 ms (8 ms ~ 800 ms)
  • Con paralelización, el tiempo promedio fue de 0.04 s

Opinión de GN⁺

• Fue impresionante el proceso de mejorar de forma gradual repitiendo intentos y errores
  • Partió de una implementación simple y en cada etapa aplicó nuevas ideas, además de optimizar
  • Aunque encontró fallos, no se rindió y buscó las causas del problema para hallar soluciones
• Sobresalió que, a pesar de su escaso conocimiento matemático previo, buscó y trató de entender los materiales relacionados
  • Aprendió conceptos matemáticos necesarios como el Pequeño Teorema de Fermat y la prueba de Miller-Rabin
  • Entendió y aplicó contenidos difíciles hasta convertirlos en implementables
• Fue notable implementar BigInt directamente para superar los límites de los tipos enteros de longitud fija
  • En lugar de usar solo una biblioteca existente, entendió el funcionamiento interno y realizó optimizaciones
  • Destacó el hecho de probar ideas diversas y mejorar de manera iterativa
• Resultó interesante que mejorara mucho el rendimiento mediante paralelización con multithreading
  • Comprendió y aprovechó bien la característica del problema, que permite cálculos independientes
  • No se trató solo de correr más rápido, sino de elegir un enfoque efectivo según la naturaleza del problema
• No alcanza un nivel criptográficamente seguro, pero se ve como un proyecto con gran valor como proceso de aprendizaje e investigación
  • Es más un reto para mostrar curiosidad y espíritu de desafío del autor que una solución de uso práctico
  • Se espera que las ideas y experiencia obtenidas en el proceso le sean de gran ayuda para su crecimiento futuro

[GN⁺]

Comentario en Hacker News

• En este contexto, varias criptomonedas usan cosas relacionadas con encontrar números primos grandes como parte de su función de prueba de trabajo. Hace alrededor de 8 años se podía ganar bastante dinero con una implementación muy rápida de prueba de primalidad. El autor fue durante un tiempo el creador y mantenedor del software de minado para Riecoin.

• En este artículo se omite la multiplicación de Montgomery, que es la mejor optimización para pruebas rápidas de primalidad. Es la base de una implementación práctica rápida de exponenciación modular.

• La CGBN que publicó Niall Emmart es realmente una biblioteca de enteros grandes para GPU extremadamente rápida. Sigue siendo la implementación batch modexp más rápida que yo conozca.

• Python incluye una bastante buena función de modexp con pow(x, y, m) → x^y % m. Gracias a ella, se puede implementar fácilmente la prueba de primalidad de Fermat o Miller-Rabin.

• Al inicio, la idea de las pruebas de primalidad probabilísticas me parecía rara, y traté de encontrar un algoritmo determinista que pudiera manejar números gigantescos; pero APR-CL y ECPP son demasiado complejos matemáticamente para entenderlos. Se hizo evidente que en casi todos los casos, incluido RSA, se usa un algoritmo probabilístico.

• Hacer Miller-Rabin determinista para un rango máximo dado de valores es trivial: basta con elegir bases que, dentro de ese rango, se han demostrado que descartan todos los pseudoprimos.

• Con una sola línea de ensamblador en línea se puede simplificar la multiplicación de números gigantes. Ojalá se añadiera al lenguaje C el concepto de multiplicación extendida. Hay soporte de hardware en todas partes.

• La prueba de Fermat era suficiente porque, si el número realmente no es primo, el algoritmo no funcionaría. Pero no sé si se puede demostrar que no existen valores de P/Q no primos que permitan cifrar y descifrar mensajes con éxito.

• Me pregunto cuánto tiempo tomó el proyecto. El autor implementó Karatsuba, Toom-Cook, FFT complejo, NTT y Schönhage–Strassen. Recomienda el libro de Silverman "A Friendly Introduction to Number Theory".

• Al escribir mi propio código para multiplicar números gigantes entendí lo difícil que es convertir a operaciones reales una explicación de alto nivel de un paper matemático. Hay un pequeño problema en la explicación relacionada con la base.

• El último ajuste de sumar 2 en vez de volver a generar los números rompe un poco la seguridad. Los números primos no se distribuyen uniformemente, por lo que queda sesgado hacia el primo inmediatamente posterior al espacio entre primos más grande.

• Hay un pequeño error en la explicación del pequeño teorema de Fermat. Mencionó que a^(p-1) es divisible por p, pero en realidad debe decir que a^(p-1) - 1 es divisible por p. En términos de aritmética modular está explicado correctamente.