Classical Primality and Factoring
The Baillie-PSW Compositeness Test
The Baillie-PSW test combining a strong base-two test with a strong Lucas test, and its status as the practical standard.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0649
Baillie-PSW combines a strong pseudoprime test to base two with a strong Lucas test. No composite is known to pass it, and it is the practical standard for probable-prime testing.
The test
The Baillie-PSW test
- Trial divideBy small primes.
- Check for a perfect squareThe Lucas parameter search requires it — see perfect powers.
- Strong test base twoA strong pseudoprime test.
- Select Lucas parametersBy scanning for a non-residue discriminant.
- Strong Lucas testSee Lucas sequences.
Why it is trusted
| Property | Status |
|---|---|
| Counterexamples known | None, despite extensive search |
| Proven to have no counterexamples | No |
| Heuristic arguments for infinitely many | Yes |
| Verified below large bounds | Yes, exhaustively |
Cost
When it is not enough
For adversarial input, or where a mathematical claim depends on primality, a proof is required. See ECPP and certificates.
Combination with random bases
Some implementations add several random-base strong tests to Baillie-PSW. This guards against an adversary who has constructed a counterexample to the fixed-parameter test, at modest additional cost.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.