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

Technische Samenvatting: U-bit Collaps in Arnault Composieten

Probleemstelling
De Baillie–PSW primality test, die een Miller–Rabin test combineert met een sterke Lucas-waarschijnlijk priemtest, heeft ondanks uitgebreid onderzoek sinds 1980 geen bekende samengestelde tegenvoorbeelden gevonden. Hoewel F. Arnault kaders heeft ontwikkeld om samengestelde gehele getallen te construeren die meerdere Miller–Rabin tests passeren door specifieke priemfactorisaties te manipuleren (Carmichael-getallen), blijft het een open vraag of deze constructies kunnen worden uitgebreid om de Lucas-component te omzeilen. Dit artikel onderzoekt of Arnault-type samengestelde getallen, specifiek die zijn ontworpen om Miller–Rabin tests tot basis 11 te passeren, een meetbare "degeneratie" vertonen in de Lucas-reeks die zou kunnen wijzen op een pad naar het construeren van een Baillie–PSW pseudopriemgetal.

Methodologie
De studie maakte gebruik van een hoog-doorvoersconstructieproces om samengestelde gehele getallen $n = p_1 p_2 p_3$ van ongeveer 350 bits te genereren. De constructie volgde het Arnault-kader, waarbij werd gewaarborgd dat de priemfactoren $p_i$ voldoen aan voorwaarden waarbij $p_i - 1$ een grote gemeenschappelijke factor $f$ deelt, waardoor het samengestelde getal Miller–Rabin tests voor bases tot en met 11 kan passeren.

• Generatieschaal: Het proces draaide op een enkele-core ARM-instantie en genereerde ongeveer 7.700 Carmichael-getallen per minuut.
• Selectiecriteria: Uit deze stroom werden samengestelde getallen die alle Miller–Rabin tests tot basis 11 passeren, geïsoleerd met een opbrengstpercentage van ongeveer 0,015% (circa 20 per uur).
• Dataset: In totaal werden 200 dergelijke samengestelde getallen verzameld voor gedetailleerde analyse.
• Testen: Elk samengesteld getal werd onderworpen aan de sterke Lucas-waarschijnlijkheidstest met standaard discriminanten $D$ (gekozen zodanig dat $(D/n) = -1$).
• Metriek: De auteurs introduceerden de U-bit collapse metriek, gedefinieerd als $\delta = \log_2 n - \log_2(U_d \mod n)$, waarbij $n+1 = d \cdot 2^s$. Deze metriek kwantificeert de afwijking van de Lucas-term $U_d$ van een uniforme verdeling in $[0, n)$. Een significante collapse (grote $\delta$) zou aangeven dat de Lucas-term ongebruikelijk klein is, een noodzakelijke voorwaarde voor een sterk Lucas-pseudopriemgetal.

Belangrijkste Resultaten
De analyse van de dataset van 200 monsters leverde de volgende bevindingen op:

• Falen in het omzeilen van de Lucas-test: Alle 200 samengestelde getallen faalden de sterke Lucas-test; er werden geen sterke Lucas-pseudopriemgetallen gevonden.
• Verwaarloosbare U-bit collapse: De geobserveerde collapse-waarden waren minimaal vergeleken met de $\approx 350$ bits reductie die vereist is voor een echt pseudopriemgetal.
  • Gemiddelde $\delta$: 1,61 bits.
  • Mediaan $\delta$: 1,0 bits.
  • Maximale $\delta$: 8 bits (waargenomen in een 344-bits samengesteld getal, wat een reductie naar 336 bits vertegenwoordigt).
  • Zero Collapse: 26% van de monsters (52 samengestelde getallen) vertoonde geen meetbare collapse ($\delta = 0$), wat betekent dat hun $U_d \mod n$-waarden statistisch niet te onderscheiden zijn van willekeurige elementen in $[0, n)$.
• Onafhankelijkheid van Parameters: Correlatieanalyse toonde verwaarloosbare relaties tussen de U-bit collapse en de Arnault-constructieparameters ($k$, $M$) of de bitgrootte van het samengestelde getal ($|\rho| < 0,09$).
• Residu-patronen: Hoewel bepaalde residuklassen modulo 35 (bijv. 2, 8, 18, 22, 23, 32) frequent voorkwamen onder de priemfactoren, domineerde geen enkel patroon de dataset en correleerden deze patronen niet met Lucas-resistentie.

Betekenis en Claims
Het artikel concludeert dat de algebraïsche voorwaarden die samengestelde getallen in staat stellen om de Miller–Rabin tests tot basis 11 te omzeilen, geen betekenisvolle vooruitgang bieden naar het omzeilen van de sterke Lucas-test. De auteurs stellen dat de twee componenten van de Baillie–PSW test fundamenteel onafhankelijke algebraïsche structuren targeten.

• Orthogonaliteit: De resultaten bieden sterk empirisch bewijs voor de orthogonaliteit van de Miller–Rabin en de Lucas-tests. De "collapse" die nodig is om de Lucas-test te breken, is geen bijproduct van de methoden die gebruikt worden om de Miller–Rabin test te breken.
• Robuustheid van Baillie–PSW: De afwezigheid van significante U-bit collapse, zelfs in een hoog-volume steekproef van samengestelde getallen die specifiek zijn ontworpen om Miller–Rabin te weerstaan, versterkt de voortdurende betrouwbaarheid van de Baillie–PSW test.
• Implicaties voor Constructie: De studie suggereert dat het construeren van een Baillie–PSW pseudopriemgetal kwalitatief andere algebraïsche beperkingen vereist dan die aangetroffen in standaard Carmichael of Arnault-constructies. Het artikel stelt dat de geobserveerde minimale collapse de fundamentele beperkingen van de huidige constructieparadigma reflecteert, in plaats van een gebrek aan computationele inspanning.

Conclusie
Deze computationele studie stelt vast dat het Arnault-raamwerk, hoewel effectief voor het genereren van Miller–Rabin pseudopriemgetallen, faalt in het produceren van samengestelde getallen met de noodzakelijke Lucas-reeks degeneratie om de Baillie–PSW test uit te dagen. De introductie van de U-bit collapse metriek biedt een kwantitatief kader voor toekomstig onderzoek, hoewel de data suggereert dat alternatieve constructiemethoden buiten het Arnault-paradigma nodig kunnen zijn om het openstaande probleem van het vinden van een Baillie–PSW tegenvoorbeeld aan te pakken.