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

Technical Summary: U-Bit Collapse in Arnault Composites

Problem Statement
The Baillie–PSW primality test, which combines a Miller–Rabin test with a strong Lucas probable prime test, has no known composite counterexamples despite extensive searches since 1980. While F. Arnault developed frameworks to construct composite integers that pass multiple Miller–Rabin tests by engineering specific prime factorizations (Carmichael numbers), it remains an open question whether these constructions can be extended to evade the Lucas component. This paper investigates whether Arnault-type composites, specifically those engineered to pass Miller–Rabin tests up to base 11, exhibit any measurable "degeneracy" in the Lucas sequence that would suggest a pathway toward constructing a Baillie–PSW pseudoprime.

Methodology
The study utilized a high-throughput construction process to generate composite integers $n = p_1 p_2 p_3$ of approximately 350 bits. The construction adhered to the Arnault framework, ensuring that the prime factors $p_i$ satisfy conditions where $p_i - 1$ shares a large common factor $f$, allowing the composite to pass Miller–Rabin tests for bases up to 11.

• Generation Scale: The process ran on a single-core ARM instance, generating approximately 7,700 Carmichael numbers per minute.
• Selection Criteria: From this stream, composites passing all Miller–Rabin tests through base 11 were isolated at a yield rate of roughly 0.015% (approx. 20 per hour).
• Dataset: A total of 200 such composites were collected for detailed analysis.
• Testing: Each composite was subjected to the strong Lucas probable prime test using standard discriminants $D$ (selected such that $(D/n) = -1$).
• Metric: The authors introduced the U-bit collapse metric, defined as $\delta = \log_2 n - \log_2(U_d \mod n)$, where $n+1 = d \cdot 2^s$. This metric quantifies the deviation of the Lucas term $U_d$ from a uniform distribution in $[0, n)$. A significant collapse (large $\delta$) would indicate the Lucas term is unusually small, a necessary condition for a strong Lucas pseudoprime.

Key Results
The analysis of the 200-sample dataset yielded the following findings:

• Failure to Evade Lucas Test: All 200 composites failed the strong Lucas test; no strong Lucas pseudoprimes were found.
• Negligible U-bit Collapse: The observed collapse values were minimal compared to the $\approx 350$ bits of reduction required for a true pseudoprime.
  • Mean $\delta$: 1.61 bits.
  • Median $\delta$: 1.0 bits.
  • Maximum $\delta$: 8 bits (observed in a 344-bit composite, representing a reduction to 336 bits).
  • Zero Collapse: 26% of the samples (52 composites) showed no measurable collapse ($\delta = 0$), meaning their $U_d \mod n$ values were statistically indistinguishable from random elements in $[0, n)$.
• Independence of Parameters: Correlation analysis revealed negligible relationships between the U-bit collapse and the Arnault construction parameters ($k$, $M$) or the composite bit-size ($|\rho| < 0.09$).
• Residue Patterns: While certain residue classes modulo 35 (e.g., 2, 8, 18, 22, 23, 32) appeared frequently among the prime factors, no single pattern dominated the dataset, and these patterns did not correlate with Lucas resistance.

Significance and Claims
The paper concludes that the algebraic conditions enabling composites to evade Miller–Rabin tests up to base 11 provide no meaningful progress toward evading the strong Lucas test. The authors argue that the two components of the Baillie–PSW test target fundamentally independent algebraic structures.

• Orthogonality: The results provide strong empirical evidence for the orthogonality of the Miller–Rabin and Lucas tests. The "collapse" required to break the Lucas test is not a byproduct of the construction methods used to break the Miller–Rabin test.
• Robustness of Baillie–PSW: The absence of significant U-bit collapse, even in a high-volume sample of composites specifically engineered to resist Miller–Rabin, reinforces the continued reliability of the Baillie–PSW test.
• Construction Implications: The study suggests that constructing a Baillie–PSW pseudoprime would require satisfying qualitatively different algebraic constraints than those found in standard Carmichael or Arnault constructions. The paper posits that the observed minimal collapse reflects fundamental limitations of the current construction paradigm rather than a lack of computational effort.

Conclusion
This computational study establishes that the Arnault framework, while effective for generating Miller–Rabin pseudoprimes, fails to produce composites with the necessary Lucas sequence degeneracy to challenge the Baillie–PSW test. The introduction of the U-bit collapse metric offers a quantitative framework for future investigations, though the data suggests that alternative construction methods beyond the Arnault paradigm may be necessary to address the open problem of finding a Baillie–PSW counterexample.