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

Sintesi Tecnica: Collasso dei bit U in Arnault Composites

Enunciato del Problema
Il test di primalità Baillie–PSW, che combina un test di Miller–Rabin con un test di probabile primo di Lucas forte, non ha controesempi composti noti nonostante le estese ricerche condotte dal 1980. Sebbene F. Arnault abbia sviluppato framework per costruire interi composti che superano molteplici test di Miller–Rabin mediante l'ingegnerizzazione di specifiche fattorizzazioni prime (numeri di Carmichael), rimane un interrogativo aperto se tali costruzioni possano essere estese per eludere la componente di Lucas. Questo documento investiga se i composti di tipo Arnault, specificamente quelli progettati per superare i test di Miller–Rabin fino alla base 11, esibiscano una "degenerazione" misurabile nella sequenza di Lucas che suggerisca una via verso la costruzione di un pseudoprimo Baillie–PSW.

Metodologia
Lo studio ha utilizzato un processo di costruzione ad alto throughput per generare interi composti $n = p_1 p_2 p_3$ di circa 350 bit. La costruzione aderiva al framework di Arnault, garantendo che i fattori primi $p_i$ soddisfacessero le condizioni per cui $p_i - 1$ condivide un grande fattore comune $f$, permettendo al composto di superare i test di Miller–Rabin fino alla base 11.

• Scala di Generazione: Il processo è stato eseguito su un'istanza ARM a core singolo, generando circa 7.700 numeri di Carmichael al minuto.
• Criteri di Selezione: Da questo flusso, sono stati isolati i composti che superavano tutti i test di Miller–Rabin fino alla base 11 con un tasso di resa di circa lo 0,015% (circa 20 all'ora).
• Dataset: Un totale di 200 tali composti è stato raccolto per un'analisi dettagliata.
• Testing: Ogni composto è stato sottoposto al test di probabile primo di Lucas forte utilizzando discriminanti $D$ standard (scelti tali che $(D/n) = -1$).
• Metrica: Gli autori hanno introdotto la metrica del collasso dei bit U, definita come $\delta = \log_2 n - \log_2(U_d \mod n)$, dove $n+1 = d \cdot 2^s$. Questa metrica quantifica la deviazione del termine di Lucas $U_d$ da una distribuzione uniforme in $[0, n)$. Un collasso significativo (grande $\delta$) indicherebbe che il termine di Lucas è insolitamente piccolo, una condizione necessaria per un pseudoprimo forte di Lucas.

Risultati Chiave
L'analisi del dataset di 200 campioni ha prodotto i seguenti risultati:

• Fallimento nell'eludere il test di Lucas: Tutti i 200 composti hanno fallito il test di Lucas forte; non sono stati trovati pseudoprimi di Lucas forti.
• Collasso dei bit U trascurabile: I valori di collasso osservati sono stati minimi rispetto ai circa 350 bit di riduzione richiesti per un vero pseudoprimo.
  • Media $\delta$: 1,61 bit.
  • Mediana $\delta$: 1,0 bit.
  • Massimo $\delta$: 8 bit (osservato in un composto a 344 bit, che rappresenta una riduzione a 336 bit).
  • Collasso Zero: Il 26% dei campioni (52 composti) ha mostrato un collasso nullo ($\delta = 0$), il che significa che i valori di $U_d \mod n$ erano statisticamente indistinguibili da elementi casuali in $[0, n)$.
• Indipendenza dai Parametri: L'analisi di correlazione ha rivelato relazioni trascurabili tra il collasso dei bit U e i parametri di costruzione di Arnault ($k$, $M$) o la dimensione in bit del composto ($|\rho| < 0,09$).
• Pattern di Residui: Sebbene certe classi di residui modulo 35 (ad es. 2, 8, 18, 22, 23, 32) apparissero frequentemente tra i fattori primi, nessun singolo pattern dominava il dataset e tali pattern non correlavano con la resistenza di Lucas.

Significatività e Rivendicazioni
Il documento conclude che le condizioni algebriche che permettono ai composti di eludere i test di Miller–Rabin fino alla base 11 non forniscono alcun progresso significativo verso l'elusione del test di Lucas forte. Gli autori sostengono che i due componenti del test Baillie–PSW mirano a strutture algebriche fondamentalmente indipendenti.

• Ortogonalità: I risultati forniscono una forte evidenza empirica dell'ortogonalità tra i test di Miller–Rabin e di Lucas. Il "collasso" necessario per rompere il test di Lucas non è un sottoprodotto dei metodi di costruzione utilizzati per rompere il test di Miller–Rabin.
• Robustezza di Baillie–PSW: L'assenza di un significativo collasso dei bit U, anche in un alto volume di composti specificamente progettati per resistere a Miller–Rabin, rafforza l'affidabilità continua del test Baillie–PSW.
• Implicazioni della Costruzione: Lo studio suggerisce che la costruzione di un pseudoprimo Baillie–PSW richiederebbe vincoli algebrici qualitativamente diversi da quelli trovati nelle standard costruzioni di Carmichael o Arnault. Il documento ipotizza che il minimo collasso osservato rifletta limitazioni fondamentali del paradigma di costruzione attuale piuttosto che una mancanza di sforzo computazionale.

Conclusione
Questo studio computazionale stabilisce che il framework di Arnault, pur essendo efficace per generare pseudoprimi di Miller–Rabin, non riesce a produrre composti con la necessaria degenerazione della sequenza di Lucas per sfidare il test Baillie–PSW. L'introduzione della metrica del collasso dei bit U offre un quadro quantitativo per indagini future, sebbene i dati suggeriscano che metodi di costruzione alternativi oltre il paradigma Arnault possano essere necessari per affrontare il problema aperto della ricerca di un controesempio Baillie–PSW.