Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

1. Planteamiento del Problema

Los sistemas de criptografía de clave pública, como RSA y Diffie-Hellman, dependen de la generación de números primos grandes. Dado que la prueba de primalidad determinista es computacionalmente costosa, las implementaciones suelen utilizar pruebas probabilísticas de compositud, como las pruebas de Solovay-Strassen o Miller-Rabin.

• El riesgo: Una prueba de primalidad puede fallar si un número compuesto (no primo) satisface la condición de la prueba para ciertas bases. Estos números se denominan pseudoprimos.
• El objetivo: Encontrar números compuestos que sobrevivan a la prueba de Solovay-Strassen para el mayor número posible de bases consecutivas (específicamente las primeras bases primas).
• El desafío: Mientras que la prueba de Miller-Rabin tiene una probabilidad de error máxima de $1/4$ por base, la prueba de Solovay-Strassen tiene un límite de $1/2$. Sin embargo, encontrar compuestos que engañen a la prueba para muchas bases consecutivas es extremadamente difícil, ya que teóricamente no existen "números de Carmichael" para el criterio de Euler (a diferencia del criterio de Fermat), lo que implica que para cualquier compuesto $n$ existe al menos una base que lo detecta.

El objetivo del artículo es construir un pseudoprimo de Euler que sobreviva a las primeras 47 bases primas (hasta el primo 211).

2. Metodología

Los autores desarrollaron un enfoque sistemático basado en la clasificación de los números de Carmichael y su multiplicación controlada.

A. Clasificación de Números de Carmichael

Utilizaron el criterio de Korselt y la función lambda de Carmichael ($\lambda(n)$) para clasificar los números de Carmichael en clases que determinan la cantidad de "mentirosos de Euler" (bases que pasan la prueba):

• Clase A: Índice $i(n) = (n-1)/\lambda(n)$ es par. Estos números tienen exactamente $\phi(n)/2$ mentirosos de Euler (el máximo teórico posible). Todos tienen símbolo de Jacobi $+1$.
• Clase B: Índice $i(n)$ es impar. Se subdividen en:
  • B1: Donde la valoración 2-adica de $\lambda(n)$ coincide con la de un subconjunto de factores primos ($h < k$). Tienen menos mentirosos.
  • B2: Donde coincide con todos los factores ($h=k$). Tienen una distribución mixta de símbolos de Jacobi.

Conclusión clave: La Clase A es la más prometedora, ya que ofrece la mayor densidad de bases que pasan la prueba.

B. Estrategia de Multiplicación

En lugar de buscar números aleatorios, los autores multiplicaron pseudoprimos de Euler ya encontrados para crear números más grandes y robustos.

1. Entrada: Utilizaron una lista filtrada de números de Carmichael "atómicos" (no productos de otros números de Carmichael) con factores primos mayores a 150.
2. Filtro de Clase A: Se enfocaron estrictamente en multiplicar números de la Clase A con otros de la Clase A.
3. Condición de Producto: Demostraron (Lema 12 y 13) que si se multiplican dos números de Carmichael de Clase A ($n_1, n_2$) que sobreviven hasta la misma base $a$, y el producto $n = n_1 n_2$ es también un número de Carmichael de Clase A, entonces $n$ sobrevivirá al menos hasta la siguiente base prima después de $a$.
4. Optimización: Ordenaron los datos por $v_2(\lambda(n))$ (la valoración 2-adica de la función lambda) para facilitar la verificación de las condiciones de la Clase A y descartar rápidamente productos que no cumplieran los requisitos.

C. Algoritmo

Desarrollaron un algoritmo (Algoritmo 1) que:

1. Toma dos pseudoprimos de Euler de la misma clase y rango de supervivencia.
2. Verifica condiciones de divisibilidad y coprimalidad.
3. Calcula $\lambda(n)$ como el MCM de los $\lambda$ de los factores.
4. Verifica si $\lambda(n) | (n-1)$ (condición de Carmichael).
5. Si es válido, verifica el símbolo de Jacobi para las siguientes bases primas hasta encontrar el fallo.

3. Contribuciones Clave

1. Clasificación Teórica: Proporcionaron una clasificación detallada de los números de Carmichael basada en la paridad del índice y las valoraciones 2-adicas, cuantificando exactamente cuántas bases de Euler pasan la prueba para cada clase.
2. Método de Construcción: Demostraron que multiplicar pseudoprimos de Euler de la Clase A es una estrategia efectiva para generar nuevos pseudoprimos con rangos de supervivencia extendidos, superando las limitaciones de los métodos constructivos anteriores (como los de Arnault o Chernick).
3. Algoritmo Eficiente: Crearon un algoritmo optimizado que evita la fuerza bruta, utilizando propiedades algebraicas (simetría de clases, valoración 2-adica) para filtrar candidatos antes de realizar cálculos costosos.
4. Nuevos Pseudoprimos: Descubrieron miles de nuevos pseudoprimos de Euler, muchos de los cuales superan los registros anteriores.

4. Resultados

El esfuerzo computacional resultó en el descubrimiento de un pseudoprimo de Euler récord:

• El Récord: Encontraron un número compuesto de 1230 bits que sobrevive a la prueba de Solovay-Strassen para las primeras 47 bases primas.
• Límite de Supervivencia: El número pasa la prueba para todas las bases enteras desde 2 hasta 211 (el 47º número primo).
• Comparación: Este resultado supera significativamente trabajos anteriores, como el de Sorenson y Webster (12 bases para Miller-Rabin).
• Estadísticas:
  • Generaron más de 128,000 pseudoprimos que sobreviven hasta la base 37.
  • Al multiplicar pares de estos, encontraron miles que sobreviven hasta bases mayores (ej. 139, 191, 199).
  • El mejor número final se encontró tras filtrar entradas con factores primos > 300 y realizar multiplicaciones recursivas simétricas (ej. $epsp_{16}$).

Además, los autores introdujeron un nuevo tipo de compuesto llamado "Pseudoprimo Sophie Germinus" (producto de un primo $p$ y $2p-1$), que tiene $\phi(n)/4$ mentirosos de Euler, aunque no lograron superar el récord con este método.

5. Significado e Impacto

• Seguridad Criptográfica: Este trabajo demuestra que, si un atacante tiene acceso a pseudoprimos de Euler de alta calidad (como el encontrado), puede engañar a los generadores de números primos que utilizan la prueba de Solovay-Strassen con un número limitado de bases. Esto subraya la importancia de usar pruebas más robustas (como Miller-Rabin con muchas bases o pruebas deterministas) en entornos adversarios.
• Teoría de Números: El artículo profundiza en la estructura de los números de Carmichael y su relación con el criterio de Euler, proporcionando una comprensión más clara de por qué ciertos compuestos son "más falsos" que otros.
• Eficiencia Computacional: La metodología de multiplicación controlada ofrece una vía eficiente para explorar el espacio de los pseudoprimos, permitiendo encontrar números extremadamente grandes con propiedades específicas sin necesidad de búsquedas aleatorias ineficientes.

En resumen, el artículo establece un nuevo límite superior para la resistencia de los pseudoprimos de Euler, demostrando que es posible construir compuestos que parecen primos para las primeras 47 bases primas, un hito significativo en la teoría de la primalidad computacional.