U-Bit Collapse in Arnault Composites:Probing the Boundary of Strong Lucas Pseudoprimes

Resumen Técnico: Colapso de U-bits en Compuestos de Arnault

Planteamiento del Problema
La prueba de primalidad Baillie–PSW, que combina una prueba de Miller–Rabin con una prueba de probable primo fuerte de Lucas, no tiene contraejemplos compuestos conocidos a pesar de las extensas búsquedas realizadas desde 1980. Si bien F. Arnault desarrolló marcos para construir enteros compuestos que pasan múltiples pruebas de Miller–Rabin mediante la ingeniería de factorizaciones primas específicas (números de Carmichael), sigue siendo una cuestión abierta si estas construcciones pueden extenderse para evadir el componente de Lucas. Este documento investiga si los compuestos de tipo Arnault, específicamente aquellos diseñados para pasar las pruebas de Miller–Rabin hasta la base 11, exhiben alguna "degeneración" medible en la secuencia de Lucas que sugiera una vía hacia la construcción de un pseudoprimo de Baillie–PSW.

Metodología
El estudio utilizó un proceso de construcción de alto rendimiento para generar enteros compuestos $n = p_1 p_2 p_3$ de aproximadamente 350 bits. La construcción se adhirió al marco de Arnault, asegurando que los factores primos $p_i$ satisfagan condiciones donde $p_i - 1$ comparte un factor común grande $f$, permitiendo que el compuesto pase las pruebas de Miller–Rabin para bases hasta 11.

• Escala de Generación: El proceso se ejecutó en una instancia ARM de un solo núcleo, generando aproximadamente 7,700 números de Carmichael por minuto.
• Criterios de Selección: De este flujo, se aislaron los compuestos que pasaban todas las pruebas de Miller–Rabin hasta la base 11 con una tasa de rendimiento de aproximadamente 0.015% (aprox. 20 por hora).
• Conjunto de Datos: Se recolectaron un total de 200 tales compuestos para un análisis detallado.
• Pruebas: Cada compuesto fue sometido a la prueba de probable primo fuerte de Lucas utilizando discriminantes estándar $D$ (seleccionados de tal manera que $(D/n) = -1$).
• Métrica: Los autores introdujeron la métrica de colapso de U-bits, definida como $\delta = \log_2 n - \log_2(U_d \mod n)$, donde $n+1 = d \cdot 2^s$. Esta métrica cuantifica la desviación del término de Lucas $U_d$ de una distribución uniforme en $[0, n)$. Un colapso significativo (un $\delta$ grande) indicaría que el término de Lucas es inusualmente pequeño, una condición necesaria para un pseudoprimo fuerte de Lucas.

Resultados Clave
El análisis del conjunto de datos de 200 muestras arrojó los siguientes hallazgos:

• Fallo en la Evasión de la Prueba de Lucas: Los 200 compuestos fallaron la prueba de Lucas fuerte; no se encontraron pseudoprimos fuertes de Lucas.
• Colapso de U-bits Despreciable: Los valores de colapso observados fueron mínimos en comparación con los $\approx 350$ bits de reducción requeridos para un verdadero pseudoprimo.
  • $\delta$ Medio: 1.61 bits.
  • $\delta$ Mediana: 1.0 bits.
  • $\delta$ Máximo: 8 bits (observado en un compuesto de 344 bits, lo que representa una reducción a 336 bits).
  • Colapso Cero: El 26% de las muestras (52 compuestos) mostraron un colapso medible de cero ($\delta = 0$), lo que significa que sus valores de $U_d \mod n$ eran estadísticamente indistinguibles de elementos aleatorios en $[0, n)$.
• Independencia de Parámetros: El análisis de correlación reveló relaciones insignificantes entre el colapso de U-bits y los parámetros de construcción de Arnault ($k$, $M$) o el tamaño de bits del compuesto ($|\rho| < 0.09$).
• Patrones de Residuos: Aunque ciertas clases de residuos módulo 35 (por ejemplo, 2, 8, 18, 22, 23, 32) aparecieron frecuentemente entre los factores primos, ningún patrón único dominó el conjunto de datos, y estos patrones no se correlacionaron con la resistencia de Lucas.

Significancia y Reivindicaciones
El documento concluye que las condiciones algebraicas que permiten a los compuestos evadir las pruebas de Miller–Rabin hasta la base 11 no proporcionan un progreso significativo hacia la evasión de la prueba de Lucas fuerte. Los autores argumentan que los dos componentes de la prueba Baillie–PSW apuntan a estructuras algebraicas fundamentalmente independientes.

• Ortogonalidad: Los resultados proporcionan evidencia empírica sólida de la ortogonalidad de las pruebas de Miller–Rabin y de Lucas. El "colapso" requerido para romper la prueba de Lucas no es un subproducto de los métodos de construcción utilizados para romper la prueba de Miller–Rabin.
• Robustez de Baillie–PSW: La ausencia de un colapso de U-bits significativo, incluso en un alto volumen de compuestos diseñados específicamente para resistir Miller–Rabin, refuerza la confiabilidad continua de la prueba Baillie–PSW.
• Implicaciones de Construcción: El estudio sugiere que construir un pseudoprimo de Baillie–PSW requeriría satisfacer restricciones algebraicas cualitativamente diferentes a las encontradas en las construcciones estándar de Carmichael o Arnault. El documento postula que el colapso mínimo observado refleja limitaciones fundamentales del paradigma de construcción actual más que una falta de esfuerzo computacional.

Conclusión
Este estudio computacional establece que el marco de Arnault, aunque es efectivo para generar pseudoprimos de Miller–Rabin, no logra producir compuestos con la degeneración de la secuencia de Lucas necesaria para desafiar la prueba de Baillie–PSW. La introducción de la métrica de colapso de U-bits ofrece un marco cuantitativo para futuras investigaciones, aunque los datos sugieren que pueden ser necesarios métodos de construcción alternativos más allá del paradigma de Arnault para abordar el problema abierto de encontrar un contraejemplo de Baillie–PSW.