Engineering/Mathematics/Algorithm engineering
Probabilistic Primality Testing
Deciding primality is easy; producing a factorization is hard. Miller–Rabin exploits that gap by looking for a non-trivial square root of one — a structure that a prime modulus cannot supply and a composite one usually can.
- Core algorithm
- Computing
- Key generation
- ≈17 min read
- Runs in every TLS handshake
01
Executive summary
Trial division settles primality for small inputs and is hopeless beyond about twenty digits. The Fermat test uses an−1 ≡ 1 as a necessary condition, but Carmichael numbers satisfy it for every coprime base, so it can never be made reliable.
Miller–Rabin repairs this by examining the sequence of squarings that produces an−1. For a prime modulus the only square roots of 1 are ±1; for a composite with at least two distinct prime factors there are others, and observing one is a proof of compositeness. The probability that a random base fails to expose a composite is at most 1/4, so repetition drives the error down geometrically.
Fermat's little theorem — necessary but not sufficient.
Composites passing for every coprime base; infinitely many exist.
A prime modulus admits only ±1; a non-trivial root certifies compositeness.
So k independent rounds bound the error by 4^{-k}.
02
Trial division and the Fermat test
Trial division by primes up to √n is complete and certain, and costs O(√n / ln n) divisions — exponential in the bit length. It remains indispensable as a pre-filter: dividing by the primes below 1000 rejects about 80% of random odd candidates at trivial cost.
Fermat test
Pick a with 1 < a < n−1. If an−1 ≢ 1 (mod n), output composite — this is certain by Fermat's little theorem. Otherwise output probably prime. A composite passing the test for base a is a Fermat pseudoprime to that base.
Carmichael numbers make the Fermat test unrepairable
A Carmichael number is a composite n with an−1 ≡ 1 (mod n) for every a coprime to n. The smallest are 561, 1105, 1729, 2465 and 2821, and Alford, Granville and Pomerance proved in 1994 that there are infinitely many. Increasing the number of Fermat rounds does not help: every coprime base is fooled. The test can only fail by stumbling on a base sharing a factor with n, which is no more likely than trial division succeeding.
03
The Miller–Rabin test
The structural fact behind the test
If n is an odd prime then x2 ≡ 1 (mod n) implies x ≡ ±1, because ℤn is a field and X2−1 has at most two roots. If n has at least two distinct odd prime factors then, by the Chinese remainder theorem, there are at least four square roots of 1, and a non-trivial one yields a factor via gcd(x−1, n).
Miller–Rabin, one round
- write n − 1 = 2^s·m with m odd
- choose a uniformly from {2, …, n−2}
- y ← a^m mod n
- if y = 1 or y = n−1: return probably prime
- for i = 1 .. s−1:
- y ← y² mod n
- if y = n−1: return probably prime
- if y = 1: return composite // non-trivial square root of 1 found
- return composite
One modular exponentiation: O(ℓ³) bit operations classically, or Õ(ℓ²) with fast arithmetic. The squaring loop reuses the exponentiation's own intermediate values.
Error bound
For odd composite n > 9, at least 3/4 of the bases in {1,…,n−1} are witnesses to compositeness. Hence a single round errs with probability at most 1/4, and k independent rounds err with probability at most 4−k. The bound is tight only for a sparse family of composites; for random inputs the true error is vastly smaller.
Two distinct threat models
For a candidate you generated yourself from a good random source, a small number of rounds suffices: the average-case error for random ℓ-bit candidates falls far below 4−k. For a candidate supplied by someone else — a modulus in a certificate, a parameter in a protocol message — the worst case applies, because the value may have been constructed to pass. Use 64 rounds, or a proof-based test, on untrusted input.
04
Related tests and practical choices
| Test | Type | Error | Where used |
|---|---|---|---|
| Trial division | Deterministic | None | Pre-filter; small inputs |
| Fermat | Monte Carlo | Fails on Carmichael numbers | Historic; not recommended alone |
| Solovay–Strassen | Monte Carlo | ≤ 1/2 per round | Superseded by Miller–Rabin |
| Miller–Rabin | Monte Carlo | ≤ 1/4 per round | The default everywhere |
| Miller–Rabin, fixed verified bases | Deterministic below a threshold | None below the threshold | 64-bit integers: first 12–13 primes suffice |
| Baillie–PSW | Heuristic | No counterexample known below 264 | Widely used in computer algebra systems |
| Pocklington certificate | Proof | None | When the factorization of p−1 is known |
| ECPP | Proof | None | Certified primes of thousands of digits |
| AKS | Deterministic, unconditional | None | Theoretical landmark; impractical at scale |
Baillie–PSW combines a base-2 strong test with a Lucas test; the two have complementary failure modes, and no composite is known to pass both.
- Always include base 2 first when using random bases: it is the cheapest possible round on many implementations and eliminates the overwhelming majority of composites immediately.
- Use verified base sets for small inputs. Below 3.3 × 1024 the first thirteen primes as bases give a deterministic answer, exhaustively verified. This is both faster and stronger than random rounds for 64-bit work.
- Certify when the application demands it. Pocklington's criterion turns a partial factorization of p−1 into a proof of primality, which is why safe-prime generation naturally yields certified primes.
06
Implementation checklist
| Item | Requirement | Consequence if ignored |
|---|---|---|
| Pre-sieving | Trial divide by primes below ~1000 | Roughly five times more exponentiations |
| Base selection | Uniform in [2, n−2], fresh per round | Compounding argument invalid |
| Round count | Small for self-generated, 64 for untrusted input | False confidence on adversarial input |
| Exponentiation | Montgomery arithmetic, windowed | Several times slower |
| Constant time | Required if the candidate itself is secret | Timing leakage of prime factors during key generation |
| Candidate shape | Fix the top bits for exact modulus size | Modulus one bit short of the nominal size |
| Extra conditions | gcd(e, p−1) = 1 for RSA | Key generation fails later, or a weak key |
| Entropy | Cryptographic source, well seeded | Colliding primes across devices |
Order of operations that works
Draw a random odd candidate with the top two bits set → sieve against a table of small primes → one Miller–Rabin round with base 2 → the remaining rounds with random bases → check the application-specific side conditions. Most candidates die at the sieve, and almost all survivors of the base-2 round are prime, so the expensive rounds run only a handful of times per key.
07
Quick reference and FAQ
| Fact | Statement |
|---|---|
| Fermat condition | an−1 ≡ 1 (mod n) for prime n, n ∤ a |
| Carmichael numbers | Infinitely many; the smallest is 561 |
| Witness density | ≥ 3/4 of bases witness compositeness |
| Error after k rounds | ≤ 4−k worst case |
| Cost | O(kℓ3) bit operations |
| Deterministic threshold | First 13 prime bases correct below 3.3 × 1024 |
| Compositeness certificate | A non-trivial square root of 1, or a Fermat failure |
| Prime density | ≈ 2/(k ln 2) among odd k-bit integers |
Does Miller–Rabin ever declare a prime composite?
Why is the worst-case bound 1/4 when most composites do far worse?
Should the test be constant time?
What if a certified prime is required rather than a probable prime?
09
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 10.
- M. O. Rabin, 'Probabilistic algorithm for testing primality', J. Number Theory 12 (1980) 128–138.
- W. R. Alford, A. Granville and C. Pomerance, 'There are infinitely many Carmichael numbers', Annals of Mathematics 139 (1994) 703–722.
- R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005 — Chapter 3.
- NIST FIPS 186-5, Digital Signature Standard, 2023 — Appendix A on prime generation and required round counts.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: primality-testing-miller-rabinReview cycle: annual