One modular exponentiation, with the intermediate squarings inspected
Fermat's little theorem gives an immediate test: if an−1 ≢ 1 (mod n) then n is composite. Carmichael numbers defeat it for every coprime base. Miller–Rabin strengthens the test by writing n − 1 = 2sd and inspecting the sequence of squarings, exploiting the fact that a field has only two square roots of 1. At most a quarter of bases can fail to witness a composite.
Learning objectives
- State Fermat's test and the reason for its failure.
- Implement the strong probable prime test correctly.
- State the error bound and how it improves for random inputs.
- Use verified deterministic base sets for bounded ranges.
- Explain why Baillie–PSW combines two dissimilar tests.
Section 01The Fermat test and Carmichael numbers
A composite passing this for a given base is a Fermat pseudoprime to that base. Carmichael numbers pass for every coprime base — 561, 1105 and 1729 are the smallest — and there are infinitely many. The Fermat test alone is therefore not merely weak but systematically defeatable.
If gcd(a, n) > 1 the test is inapplicable, but that GCD is a non-trivial factor of n — a useful outcome for a test that was only meant to detect compositeness. Implementations should report it rather than discard it.
Section 02The strong test
In a field, x2 = 1 forces x = ±1. The strong test checks this at every squaring on the way to an−1.
- Write n − 1 = 2sd with d odd.
- Set x ← ad mod n. If x = 1 or x = n − 1, report probable prime for this base.
- For r = 1, …, s−1: set x ← x2 mod n.
- If x = n − 1, report probable prime for this base.
- If x = 1, report composite — a non-trivial square root of 1 was found. This is the strengthening over Fermat.
- Report composite.
The 1/4 bound applies to bases chosen at random. Fixed bases can be defeated by adversarially constructed composites, and such constructions are published. Any implementation used on untrusted input must randomise its bases.
Section 03Deterministic variants
For bounded ranges, exhaustively verified base sets make the test deterministic. These sets are the result of computation, not theory, and are valid only within their stated bound.
| Bound on n | Sufficient bases |
|---|---|
| 3 215 031 751 | 2, 3, 5, 7 |
| 3 474 749 660 383 | 2, 3, 5, 7, 11, 13 |
| 341 550 071 728 321 | the first 9 primes |
| 3 317 044 064 679 887 385 961 981 | the first 13 primes |
These sets are proved only up to their bounds. Applying a set beyond its range converts a deterministic test into an unsound one with no error bound at all. Above 64 bits, use random bases and report a probability, or use a proving algorithm.
Section 04Baillie–PSW
The Baillie–PSW test combines a strong probable prime test to base 2 with a strong Lucas test using parameters chosen by a Jacobi symbol condition. The two tests fail in structurally different ways, so a composite passing both would need to be exceptional in two unrelated respects.
Despite extensive search, no composite has been found that passes Baillie–PSW, though heuristic arguments suggest such numbers exist. It is not a proof of primality, but as a practical filter it is stronger than any comparable number of Miller–Rabin rounds and is the default in several major libraries.
ReferenceFrequently asked questions
Why is the error probability better in practice than 4^(-k)?
Because the 1/4 bound is attained only by rare, specially structured composites. For a random odd candidate of a given size, the probability that it is composite yet passes even a single round is far smaller, which is why candidate generation and adversarial testing require different round counts.
Should the base 1 or n-1 be used?
No — both pass trivially for every n and carry no information. Bases should be drawn uniformly from the range 2 to n−2.
Does the strong test detect all Carmichael numbers?
Yes, for most bases. Carmichael numbers are Fermat pseudoprimes to all coprime bases, but they are not strong pseudoprimes to all bases — the intermediate square root condition catches them, which is precisely why the strong test superseded Fermat's.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.