Baillie–PSW

Baillie–PSW
Name	Baillie–PSW
Type	Probabilistic primality test
Introduced	1980s
Creators	R. P. Baillie, Samuel S. Wagstaff Jr., Selfridge (contributor)
Related	Miller–Rabin primality test, Lucas probable prime test, Fermat's little theorem, BPSW conjecture

Baillie–PSW Baillie–PSW is a hybrid probabilistic primality test combining a strong Fermat's little theorem-based witness check and a strong Lucas probable prime test originally proposed to detect composite integers efficiently. The test is widely used in software libraries and cryptographic toolkits where rapid screening of candidate primes is required, and it is notable for having no known counterexamples among integers below very large bounds. Baillie–PSW is connected historically and practically to methods developed by R. P. Baillie, Samuel S. Wagstaff Jr., and contributions attributed to John Selfridge.

Overview

Baillie–PSW is conventionally a two-stage procedure: a strong Miller–Rabin primality test with base 2 followed by a strong Lucas probable prime test with parameters chosen by a quadratic character rule. The test is intended to be a fast filter in implementations used by GNU Project, OpenSSL, Python (programming language), and other LibreSSL-based projects where primality screening for cryptographic key generation is critical. In the absence of counterexamples, Baillie–PSW is treated in practice like a deterministic test for integers used in RSA, Diffie–Hellman, and similar Elliptic curve cryptography contexts despite lacking a formal proof equivalent to AKS primality test.

Definitions and Algorithmic Criteria

The Baillie–PSW procedure begins with a strong Fermat probable prime check often realized as a strong Miller–Rabin test to base 2, followed by the selection of a quadratic discriminant D using a sequence akin to criteria employed by Selfridge: D is chosen from {5, −7, 9, −11, ...} so that the Jacobi symbol (D|n) = −1, which references arithmetic objects studied in Carl Friedrich Gauss's work on quadratic reciprocity and in Adrien-Marie Legendre symbol theory. The Lucas stage uses parameters P = 1 and Q = (1 − D)/4 to execute a strong Lucas probable prime check, related to the sequence theory of Édouard Lucas and linked to concepts in Fibonacci-type recurrences. The combined criterion declares a number probable prime only if it passes both stages; failing either stage certifies compositeness.

Historical Development and Contributors

The combined test traces lineage to separate contributions: the strong Fermat-based tests popularized by Gary Miller and Michael Rabin, the Lucas tests formalized by Édouard Lucas and modernized by Selfridge, and the explicit hybrid suggested through correspondence and publications by R. P. Baillie and Samuel S. Wagstaff Jr.. Later computational searches and theoretical commentary involved researchers affiliated with institutions such as University of Waterloo, Massachusetts Institute of Technology, and University of Illinois Urbana–Champaign. Discussions of reliability and reported bounds have been engaged by authors connected to CWI (Centrum Wiskunde & Informatica), Bell Labs, and independent mathematicians publishing in venues like Mathematics of Computation and proceedings associated with International Congress of Mathematicians-level conferences.

Implementation and Computational Use

Practical implementations of the Baillie–PSW test appear in libraries for languages and systems including C (programming language), C++, Python (programming language), Go (programming language), and Rust (programming language), and in applications run on infrastructures managed by GitHub, Debian, and FreeBSD. Implementers must handle modular exponentiation efficiently using algorithms related to those by Peter L. Montgomery and reconcile Lucas sequence evaluation with fast doubling techniques akin to approaches in Elliptic curve scalar multiplication. Optimizations often involve multi-precision backends like GNU Multiple Precision Arithmetic Library and hardware-aware routines targeting platforms such as x86-64, ARM, and PowerPC.

Empirical Results and Known Exceptions

Extensive empirical searches have found no composite integer that passes the full Baillie–PSW test within ranges tested by projects run on clusters at Google, Microsoft Research, and academic grids associated with Princeton University and University of Cambridge. Heuristic analyses referencing work by Pomerance, Selfridge, and Wagstaff suggest extreme rarity of counterexamples if any exist. A small number of composites are known to pass only the first stage (Miller–Rabin base 2) or only the Lucas stage, with documented examples appearing in literature from Mathematics of Computation and technical reports originating at Bell Labs and AT&T Labs. No published composite integer is currently verified to pass both stages, and searches continue using distributed projects akin to Great Internet Mersenne Prime Search-style computations.

Mathematical Analysis and Heuristics

Mathematical reasoning around Baillie–PSW invokes properties of pseudoprimes studied by Poulet, Carmichael, and modern analyses by Pomerance and Erdős. Heuristics draw on density estimates for strong pseudoprimes to random bases as developed by Monier and Rabin, and on distributional results in algebraic number theory linked to Chebotarev density theorem and quadratic character behavior examined in the work of Dirichlet and Hecke. Formal proofs that no counterexample exists would likely require breakthroughs connecting residue class properties elucidated by Galois theory and analytic estimates of the type pursued by Vinogradov and Selberg. Until such results appear, Baillie–PSW remains a highly practical but unproven composite-free composite filter relied upon across computational and cryptographic communities.

Category:Primality tests