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

Technisches Resümee: U-Bit-Kollaps bei Arnault-Kompositen

Problemstellung
Der Baillie–PSW-Primzahltest, der einen Miller–Rabin-Test mit einem starken Lucas-wahrscheinlichen Primzahltest kombtiniert, weist trotz intensiver Untersuchungen seit 1980 keine bekannten zusammengesetzten Gegenbeispiele auf. Während F. Arnault Frameworks entwickelte, um zusammengesetzte Zahlen zu konstruieren, die mehrere Miller–Rabin-Tests bestehen, indem er spezifische Primfaktorzerlegungen (Carmichael-Zahlen) technisch manipuliert, bleibt es eine offene Frage, ob diese Konstruktionen erweitert werden können, um die Lucas-Komponente zu umgehen. Diese Arbeit untersucht, ob Arnault-Typen von Kompositen – speziell jene, die darauf ausgelegt sind, Miller–Rabin-Tests bis zur Basis 11 zu bestehen – eine messbare „Degenerierung“ in der Lucas-Folge aufweisen, die auf einen Pfad zur Konstruktion einer Baillie–PSW-Pseudoprimzahl hindeuten würde.

Methodik
Die Studie nutzte einen Hochdurchsatz-Konstruktionsprozess, um zusammengesetzte Zahlen $n = p_1 p_2 p_3$ von etwa 350 Bit zu generieren. Die Konstruktion folgte dem Arnault-Framework, wobei sichergestellt wurde, dass die Primfaktoren $p_i$ die Bedingungen erfüllen, dass $p_i - 1$ einen großen gemeinsamen Faktor $f$ teilt, was es der zusammengesetzten Zahl ermöglicht, Miller–Rabin-Tests für Basen bis zu 11 zu bestehen.

• Generierungsskala: Der Prozess lief auf einer Single-Core ARM-Instanz und generierte etwa 7.700 Carmichael-Zahlen pro Minute.
• Selektionskriterien: Aus diesem Strom wurden Komposite, die alle Miller–Rabin-Tests bis Basis 11 bestanden, mit einer Ausbeute von etwa 0,015 % (ca. 20 pro Stunde) isoliert.
• Datensatz: Insgesamt wurden 200 dieser Komposite für eine detaillierte Analyse gesammelt.
• Testung: Jede zusammengesetzte Zahl wurde dem starken Lucas-wahrscheinlichen Primzahltest mit Standard-Diskriminanten $D$ (gewählt, sodass $(D/n) = -1$) unterzogen.
• Metrik: Die Autoren führten die U-Bit-Kollaps-Metrik ein, definiert als $\delta = \log_2 n - \log_2(U_d \mod n)$, wobei $n+1 = d \cdot 2^s$. Diese Metrik quantifiziert die Abweichung des Lucas-Terms $U_d$ von einer Gleichverteilung in $[0, n)$. Ein signifikanter Kollaps (großes $\delta$) würde darauf hindeuten, dass der Lucas-Term ungewöhnlich klein ist, eine notwendige Bedingung für eine starke Lucas-Pseudoprimzahl.

Wesentliche Ergebnisse
Die Analyse des 200-Proben-Datensatzes lieferte die folgenden Erkenntnisse:

• Versagen beim Umgehen des Lucas-Tests: Alle 200 Komposite scheiterten am starken Lucas-Test; es wurden keine starken Lucas-Pseudoprimzahlen gefunden.
• Vernachlässigbarer U-Bit-Kollaps: Die beobachteten Kollaps-Werte waren minimal im Vergleich zu den $\approx 350$ Bits Reduktion, die für eine echte Pseudoprimzahl erforderlich wären.
  • Mittleres $\delta$: 1,61 Bits.
  • Median $\delta$: 1,0 Bits.
  • Maximales $\delta$: 8 Bits (beobachtet bei einem 344-Bit-Kompositen, was einer Reduktion auf 336 Bits entspricht).
  • Null-Kollaps: 26 % der Proben (52 Komposite) zeigten keinen messbaren Kollaps ($\delta = 0$), was bedeutet, dass ihre $U_d \mod n$-Werte statistisch ununterscheidbar von zufälligen Elementen in $[0, n)$ sind.
• Unabhängigkeit der Parameter: Eine Korrelationsanalyse ergab vernachlässigbare Beziehungen zwischen dem U-Bit-Kollaps und den Arnault-Konstruktionsparametern ($k$, $M$) oder der Bit-Größe der zusammengesetzten Zahl ($|\rho| < 0,09$).
• Residuenmuster: Während bestimmte Residuenklassen modulo 35 (z. B. 2, 8, 18, 22, 23, 32) häufig unter den Primfaktoren auftraten, dominierte kein einzelnes Muster den Datensatz, und diese Muster korrelierten nicht mit der Lucas-Resistenz.

Bedeutung und Behauptungen
Die Arbeit kommt zu dem Schluss, dass die algebraischen Bedingungen, die es zusammengesetzten Zahlen ermöglichen, Miller–Rabin-Tests bis zur Basis 11 zu umgehen, keinen nennenswerten Fortschritt darstellt, um den starken Lucas-Test zu umgehen. Die Autoren argumentieren, dass die beiden Komponenten des Baillie–PSW-Tests grundlegend unabhängige algebraische Strukturen ansprechen.

• Orthogonalität: Die Ergebnisse liefern starke empirische Belege für die Orthogonalität der Miller–Rabin- und der Lucas-Tests. Der „Kollaps“, der erforderlich ist, um den Lucas-Test zu brechen, ist kein Nebenprodukt der Konstruktionsmethoden, die verwendet werden, um den Miller–Rabin-Test zu brechen.
• Robustheit von Baillie–PSW: Das Fehlen eines signifikanten U-Bit-Kollapses, selbst bei einer hohen Anzahl von Kompositen, die speziell zur Resistenz gegen Miller–Rabin konstruiert wurden, untermauert die anhaltende Zuverlässigkeit des Baillie–PSW-Tests.
• Implikationen für die Konstruktion: Die Studie legt nahe, dass die Konstruktion einer Baillie–PSW-Pseudoprimzahl qualitativ unterschiedliche algebraische Zwänge erfordert als die, die in Standard-Carmichael- oder Arnault-Konstruktionen zu finden sind. Die Autoren postulieren, dass der beobachtete minimale Kollaps die fundamentalen Grenzen des aktuellen Konstruktionsparadigmas widerspiegelt und nicht auf einen Mangel an Rechenleistung zurückzuführen ist.

Fazit
Diese computergestützte Studie stellt fest, dass das Arnault-Framework, obwohl effektiv für die Generierung von Miller–Rabin-Pseudoprimzahlen, nicht in der Lage ist, Komposite mit der notwendigen Degenerierung der Lucas-Folge zu erzeugen, um den Baillie–PSW-Test infrage zu stellen. Die Einführung der U-Bit-Kollaps-Metrik bietet einen quantitativen Rahmen für zukünftige Untersuchungen, wenngleich die Daten darauf hindeuten, dass alternative Konstruktionsmethoden jenseits des Arnault-Paradigmas notwendig sein könnten, um das offene Problem eines Baillie–PSW-Gegenbeispiels anzugehen.