Engineering / Mathematics — Primality Testing
The Miller-Rabin Primality Test
The Miller-Rabin test, the witness structure, the one-quarter bound, and why it is the practical standard.
Executive summary
Miller-Rabin strengthens the Fermat test by tracking the square roots of unity encountered during exponentiation. No composite passes for more than a quarter of bases.
That bound is worst case and unconditional, which makes the test reliable even on adversarially chosen candidates.
Learning objectives
- State the algorithm and the witness condition.
- State and interpret the one-quarter bound.
- Choose the number of rounds for a target error.
01The algorithm
Miller-Rabin test
odd candidate n > 3, random base acomposite (certain), or probably prime- Write n − 1 = 2^s · d with d odd.
- Choose a base a uniformly from {2, ..., n−2}.
- Compute x = a^d mod n.
- If x = 1 or x = n−1, report probably prime.
- Repeat s−1 times: set x = x² mod n; if x = n−1, report probably prime.
- Report composite.
one modular exponentiation, O(len(n)³)The logic: if n is prime then a^{n−1} = 1, and the sequence of squarings reaching it must pass through −1 if it does not start at 1, because ±1 are the only square roots of unity modulo a prime. Failing to observe this proves compositeness.
02The witness bound
Witness density
If n is an odd composite greater than 3, then at least three quarters of the bases in {2, ..., n−2} are witnesses to its compositeness.
Consequently a single round errs with probability at most 1/4, and k independent rounds err with probability at most 4^{−k}.
The proof shows that the non-witnesses are contained in a proper subgroup of Z_n*, and a proper subgroup of a finite group contains at most half its elements — with a more careful argument tightening this to a quarter.
- 1 round
≤ 2^{−2}Insufficient alone - 10 rounds
≤ 2^{−20}Adequate for non-adversarial input - 40 rounds
≤ 2^{−80}Standard for cryptographic use - 64 rounds
≤ 2^{−128}Conservative; cost is negligible in context
03Deterministic variants
If the base is not chosen randomly but from a fixed set, the test becomes deterministic and the probabilistic bound no longer applies.
| Bound on n | Sufficient fixed bases | Status |
|---|---|---|
| < 3,215,031,751 | 2, 3, 5, 7 | Verified exhaustively |
| < 3.3 × 10²⁴ | First 13 primes | Verified exhaustively |
| All n, under GRH | Bases up to 2(ln n)² | Conditional on the generalised Riemann hypothesis |
04Frequently asked questions
Why is the bound one quarter rather than one half?
The subgroup argument gives one half directly. Tightening to one quarter requires a finer analysis of the possible structures of the non-witness set, and the improvement matters because it halves the rounds needed for a target error.
Is 40 rounds excessive?
For locally generated candidates, yes by a wide margin — a handful suffices in practice. It is retained because the cost is trivial relative to key generation as a whole and it covers the adversarial case without further thought.
Can Miller-Rabin prove primality?
No. Passing establishes only a probability bound. Proving primality requires a different method such as elliptic curve primality proving or AKS, both far more expensive.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 247-252.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.