The Miller–Rabin primality test is a primality-testing algorithm that determines whether an integer is composite or is a probable prime. It applies necessary conditions for primality to a sequence of modular powers. A failed condition proves that the input is composite; passing the test does not, by itself, prove that it is a prime number. For any fixed odd composite input, one independently and uniformly chosen test base has a probability of less than or equal to of failing to expose its compositeness. Repeating the test with independent random bases reduces this error bound exponentially.
The test is widely used in computational number theory and cryptographic prime generation because it is fast, straightforward to implement, and effective on very large integers.
Mathematical basis
Let be an odd integer. Write
where is odd and . For a chosen integer base , with , consider the sequence in modular arithmetic
Each term after the first is obtained by squaring the preceding term modulo .
If is prime, Fermat’s little theorem gives
Moreover, modulo a prime, the only square roots of are and . This follows because the residue classes form a finite field, in which
implies or .
Consequently, if is prime, either
or
These alternatives are the strong probable-prime condition to base . If neither holds, must be composite.
An equivalent interpretation starts at the final term, which must be for a prime, and works backward through the squaring chain. Unless the initial term is already , the chain must reach its first by squaring . Reaching by squaring any other residue reveals behavior impossible modulo a prime.
Algorithm
Inputs below are not prime. The integers and are prime, and any larger even integer is composite. For the remaining odd inputs, the test proceeds as follows.
MillerRabin(n, k):
if n < 2:
return NOT PRIME
if n = 2 or n = 3:
return PRIME
if n is even:
return COMPOSITE
write n - 1 = 2^s * d with d odd
repeat k times:
choose a uniformly at random from {2, ..., n - 2}
x = a^d mod n
if x = 1 or x = n - 1:
continue to the next round
passed = false
repeat s - 1 times:
x = x^2 mod n
if x = n - 1:
passed = true
break
if x = 1:
return COMPOSITE
if not passed:
return COMPOSITE
return PROBABLY PRIME
Here is a positive integer specifying the number of rounds. The initial power is computed using modular exponentiation, rather than by constructing the enormous integer .
An optional preliminary greatest common divisor computation can detect a factor immediately: if , then is composite. This check is not required for the correctness of the usual algorithm.
Testing divisibility by a small collection of primes before running Miller–Rabin often reduces the total work when screening many candidates.
Witnesses, liars, and strong pseudoprimes
A base that causes the test to reject is called a strong witness to compositeness, or simply a Miller–Rabin witness. If is composite but passes for a particular base, that base is a strong liar, and is a strong pseudoprime to that base.
These terms describe the relationship between a number and a base. A composite number may pass for one base and fail for another.
Example: detecting a Fermat pseudoprime
Consider
For base ,
and the next square is
The initial value is neither nor , and the squaring step reaches without first reaching . Miller–Rabin therefore proves that is composite.
Nevertheless,
so passes the simpler Fermat test to base . Miller–Rabin extracts more information from the intermediate powers.
The nontrivial square root of also exposes factors:
Such factor recovery is sometimes possible, although a Miller–Rabin witness need not directly yield a factor.
Example: a passing composite
The composite integer
passes the test to base . Here , and
Thus, a single successful round cannot establish primality.
Error guarantee and its interpretation
For every odd composite , the number of strong liars among bases is at most . The smaller odd composite is also easily handled, and the standard sampling interval gives the familiar per-round error bound of at most .
For a fixed composite input and independently and uniformly sampled bases,
For example, rounds give a worst-case bound of
The guarantee is one-sided:
- A prime input always passes, assuming correct arithmetic and implementation.
- A composite input may pass, but its probability of doing so is bounded under the stated sampling assumptions.
In the terminology of randomized algorithms, Miller–Rabin is a one-sided-error Monte Carlo algorithm.
The direction of this conditional probability matters. The bound is not automatically the probability that an accepted number is composite:
also depends on how candidates were selected and their initial frequency of primality. It is a different quantity from the probability that a fixed composite passes.
The repetition bound relies on independent, uniform base selection. Repeating the same base gives no additional mathematical assurance, and arbitrary predictable base choices do not acquire the guarantee merely because there are of them.
Deterministic versions
Although the general-purpose test is randomized, Miller–Rabin can be made deterministic in several settings.
Bounded input ranges
For a specified finite range of integers, proven sets of bases suffice to distinguish every prime from every composite in that range. For example, testing the twelve prime bases
is sufficient for inputs , with the usual handling of small inputs.
An implementation using a fixed base list must treat bases outside the ordinary sampling interval correctly, for example by reducing them modulo and handling trivial residues. The bounded-range theorem must also match the actual input range. A base set sufficient for 64-bit integers is not thereby sufficient for arbitrary-precision integers.
Conditional deterministic testing
Miller’s original approach gives a deterministic polynomial-time test under an appropriate form of the generalized Riemann hypothesis. Under that assumption, every odd composite has a witness among bases bounded by a constant multiple of , so checking all bases up to that bound suffices.
Without the hypothesis, the same small-base bound is not known to hold generally. Unconditional deterministic polynomial-time primality algorithms exist, but they use different methods.
Computational cost
Let be the bit length of . Binary modular exponentiation requires modular multiplications, and the subsequent squaring chain also takes at most modular multiplications.
With schoolbook integer arithmetic, a round therefore requires
bit operations, and rounds require
These expressions use asymptotic notation. Faster multiplication and modular-reduction methods improve the bit complexity. More generally, if modular multiplication of -bit values costs , the cost is approximately .
Many composite candidates are rejected during the first round, so they do not incur the cost of all rounds. Prime inputs pass every round and therefore require the full prescribed computation.
History and practical role
Gary L. Miller published the deterministic, hypothesis-dependent foundation in 1976. Michael O. Rabin published the randomized formulation in 1980, using the fact that a large fraction of bases reveal every odd composite.
Miller–Rabin became a standard tool for generating large probable primes. A typical process produces candidates of a desired bit length, eliminates those divisible by small primes, and applies several Miller–Rabin rounds to the survivors. The prime number theorem explains why primes remain sufficiently frequent among large integers for repeated candidate generation to be practical.
The test has several important limitations:
- Probable primality is not a primality proof. Passing random rounds provides a quantified error bound, not a general proof of primality.
- The arithmetic must be exact. Overflow in fixed-width multiplication can invalidate modular computations, even when the mathematical algorithm is correct.
- The base-selection procedure is part of the guarantee. Biased or dependent selections require separate analysis.
- Witness detection is not general factorization. A rejected candidate is known to be composite, but its factors may remain unknown.
- Fixed bases have bounded guarantees. A proven finite base set must not be extended beyond its established range without justification.
Where a verifiable primality certificate is required, Miller–Rabin can serve as a preliminary filter before a separate primality-proving procedure.