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

Résumé Technique : Effondrement de l'U-bit dans les Composés d'Arnault

Énoncé du Problème
Le test de primalité de Baillie–PSW, qui combine un test de Miller–Rabin avec un test de probabilité de premier de Lucas fort, n'a aucun contreexemple composé connu malgré des recherches intensives depuis 1980. Bien que F. Arnault ait développé des cadres pour construire des entiers composés qui réussissent plusieurs tests de Miller–Rabin en concevant des factorisations premières spécifiques (nombres de Carmichael), la question de savoir si ces constructions peuvent être étendues pour échapper au composant de Lucas reste ouverte. Ce document examine si les composés de type Arnault, spécifiquement ceux conçus pour réussir les tests de Miller–Rabin jusqu'à la base 11, présentent une « dégénérescence » mesurable dans la suite de Lucas qui suggérerait une voie vers la construction d'un pseudoprime de Baillie–PSW.

Méthodologie
L'étude a utilisé un processus de construction à haut débit pour générer des entiers composés $n = p_1 p_2 p_3$ d'environ 350 bits. La construction respectait le cadre d'Arnault, garantissant que les facteurs premiers $p_i$ satisfont des conditions où $p_i - 1$ partage un grand facteur commun $f$, permettant au composé de réussir les tests de Miller–Rabin pour des bases allant jusqu'à 11.

• Échelle de Génération : Le processus a été exécuté sur une instance ARM monocœur, générant environ 7 700 nombres de Carmichael par minute.
• Critères de Sélection : Des composés réussissant tous les tests de Miller–Rabin jusqu'à la base 11 ont été isolés avec un taux de rendement d'environ 0,015 % (environ 20 par heure).
• Jeu de Données : Un total de 200 composés de ce type a été collecté pour une analyse détaillée.
• Tests : Chaque composé a été soumis au test de probabilité de premier de Lucas fort avec des discriminants $D$ standards (sélectionnés tels que $(D/n) = -1$).
• Métrique : Les auteurs ont introduit la métrique d'effondrement de l'U-bit, définie par $\delta = \log_2 n - \log_2(U_d \mod n)$, où $n+1 = d \cdot 2^s$. Cette métrique quantifie l'écart du terme de Lucas $U_d$ par rapport à une distribution uniforme dans $[0, n)$. Un effondrement significatif (un $\delta$ élevé) indiquerait que le terme de Lucas est anormalement petit, une condition nécessaire pour un pseudoprime de Lucas fort.

Résultats Clés
L'analyse du jeu de données de 200 échantillons a produit les résultats suivants :

• Échec de l'Évasion du Test de Lucas : Les 200 composés ont échoué au test de Lucas fort ; aucun pseudoprime de Lucas fort n'a été trouvé.
• Effondrement de l'U-bit Négligeable : Les valeurs d'effondrement observées étaient minimales par rapport aux $\approx 350$ bits de réduction requis pour un véritable pseudoprime.
  • $\delta$ Moyen : 1,61 bits.
  • $\delta$ Médian : 1,0 bit.
  • $\delta$ Maximum : 8 bits (observé dans un composé de 344 bits, représentant une réduction à 336 bits).
  • Effondrement Zéro : 26 % des échantillons (52 composés) ne montraient aucun effondrement mesurable ($\delta = 0$), signifiant que leurs valeurs $U_d \mod n$ étaient statistiquement indiscernables d'éléments aléatoires dans $[0, n)$.
• Indépendance des Paramètres : L'analyse de corrélation a révélé des relations négligeables entre l'effondrement de l'U-bit et les paramètres de construction d'Arnault ($k$, $M$) ou la taille en bits du composé ($|\rho| < 0,09$).
• Motifs de Résidus : Bien que certaines classes de résidus modulo 35 (par exemple, 2, 8, 18, 22, 23, 32) soient apparues fréquemment parmi les facteurs premiers, aucun motif unique n'a dominé le jeu de données, et ces motifs ne corrélaient pas avec la résistance de Lucas.

Signification et Revendications
Le document conclut que les conditions algébriques permettant aux composés d'échapper aux tests de Miller–Rabin jusqu'à la base 11 ne fournissent aucun progrès significatif pour échapper au test de Lucas fort. Les auteurs soutiennent que les deux composantes du test de Baillie–PSW ciblent des structures algébriques fondamentalement indépendantes.

• Orthogonalité : Les résultats fournissent une preuve empirique forte de l'orthogonalité des tests de Miller–Rabin et de Lucas. L'effondrement requis pour briser le test de Lucas n'est pas un sous-produit des méthodes de construction utilisées pour briser le test de Miller–Rabin.
• Robustesse de Baillie–PSW : L'absence d'effondrement significatif de l'U-bit, même dans un échantillon de haute volumétrie de composés spécifiquement conçus pour résister à Miller–Rabin, renforce la fiabilité continue du test de Baillie–PSW.
• Implications de Construction : L'étude suggère que la construction de un pseudoprime de Baillie–PSW nécessiterait de satisfaire à des contraintes algébriques qualitativement différentes de celles trouvées dans les constructions standards de Carmichael ou d'Arnault. Le document avance que l'effondrement minimal observé reflète les limitations fondamentales du paradigme de construction actuel plutôt qu'un manque d'effort de calcul.

Conclusion
Cette étude computationnelle établit que le cadre d'Arnault, bien qu'efficace pour générer des pseudoprimes de Miller–Rabin, échoue à produire des composés présentant la dégénérescence de la suite de Lucas nécessaire pour défier le test de Baillie–PSW. L'introduction de la métrique d'effondrement de l'U-bit offre un cadre quantitatif pour les investigations futures, bien que les données suggèrent que des méthodes de construction alternatives au-delà du paradigme d'Arnault pourraient être nécessaires pour aborder le problème ouvert de la recherche d'un contreexemple de Baillie–PSW.