Miller–Rabin Primality Test: How It Works

The Miller–Rabin primality test checks whether an integer behaves the way a prime must behave under modular exponentiation. It is especially useful for large odd integers, where testing possible divisors one by one becomes expensive. A failed Miller–Rabin round proves that the number is composite. A passed randomized round says something different: the number has survived that test and is a probable prime for the chosen base.

Miller–Rabin is stronger than the basic Fermat primality test because it does not inspect only the final congruence an−1 ≡ 1 (mod n). It also examines the chain of repeated squarings that leads to that value. That extra structure is what exposes many composite numbers that can imitate primes in a Fermat test.

Why Miller–Rabin rewrites n − 1

For an odd integer n > 2, the number n − 1 is even. It can therefore be written uniquely in the form:

Here, d is odd and s counts how many factors of 2 can be removed from n − 1.

For example, if n = 21:

This decomposition is more than convenient notation. It turns the exponent n − 1 into a sequence that Miller–Rabin can inspect:

Each term after the first is obtained by squaring the previous value modulo n. The test watches this chain for a pattern that every prime must satisfy.

Why the squaring chain reveals composite numbers

Suppose n is prime and the chosen base a is not divisible by n. Fermat’s little theorem gives:

Now look backward through the squaring chain. Over a prime modulus, the equation

has only two solutions: x ≡ 1 and x ≡ −1. The reason is direct. If n is prime and n divides (x − 1)(x + 1), then n must divide one of those two factors.

So if the sequence for a prime eventually reaches 1, one of two things must happen. The first value a^d is already 1, or the first appearance of 1 later in the chain is immediately preceded by −1. In modular arithmetic, −1 mod n is represented by n − 1.

A composite modulus can have nontrivial square roots of 1. That allows a sequence to reach 1 through a value other than ±1, or to fail the prime pattern in another way. Miller–Rabin uses such a failure to prove compositeness for the chosen base.

One Miller–Rabin round step by step

Assume n is an odd integer greater than 2. A practical implementation normally handles small values and even numbers before starting the modular test.

1. Write n − 1 as 2^sd, with d odd.
2. Choose a base a with 2 ≤ a ≤ n − 2.
3. Compute x = a^d mod n.
4. If x = 1 or x = n − 1, the round passes.
5. Otherwise, square x modulo n, at most s − 1 times.
6. If any squared value becomes n − 1, the round passes.
7. If no such value appears, n is composite.

miller_rabin_round(n, a):
    write n - 1 as 2^s * d, with d odd
    x = a^d mod n

    if x == 1 or x == n - 1:
        return PASS

    repeat s - 1 times:
        x = x^2 mod n

        if x == n - 1:
            return PASS

    return COMPOSITE

When several bases are used, the procedure stops as soon as one base returns COMPOSITE. Only if every selected base passes does the randomized algorithm return a probable-prime result.

Example: 13 passes the test for base 2

Take n = 13. First split n − 1 into an odd part and a power of 2:

So s = 2 and d = 3. Choose base a = 2 and calculate:

The value 8 is neither 1 nor 12, so the test squares it:

Since 12 = 13 − 1, the round passes. Base 2 has found no contradiction with 13 being prime.

Example: base 2 exposes 21 as composite

Now take n = 21:

Here s = 2 and d = 5. With base a = 2:

That is neither 1 nor 20. There is one squaring step available because s − 1 = 1:

The value never becomes 20. The round therefore fails, which proves that 21 is composite. In Miller–Rabin terminology, base 2 is a witness to the compositeness of 21.

Why Miller–Rabin catches numbers the Fermat test can miss

The difference becomes clear with 341 = 11 × 31. This composite number satisfies the base-2 Fermat congruence:

A basic Fermat test using only that final equality would let 341 pass. Miller–Rabin inspects the route to 1 instead.

Since 340 = 2² × 85, start with:

Then square:

The value 32 is neither 1 nor −1 modulo 341, yet its square is 1. That is a nontrivial square root of 1, something that cannot occur modulo a prime. Miller–Rabin therefore identifies 341 as composite even though the final Fermat congruence looks correct.

Witnesses, strong pseudoprimes, and strong liars

The terminology matters because a passed round and a proven prime are not the same statement.

A composite number may have some strong liars, which is why a single passing base does not generally prove primality. The useful mathematical bound is that for an odd composite candidate, at most one quarter of the possible bases can make it pass a Miller–Rabin round.

How repeated rounds reduce the error bound

If bases are selected independently and uniformly, the one-quarter bound compounds across rounds. For a fixed composite number, the chance that it survives k independent Miller–Rabin rounds is bounded by:

This distinction is easy to miss. Miller–Rabin provides a bound on the test’s behavior under random base selection, not a direct percentage label for the primality of every number that passes.

Random bases and deterministic Miller–Rabin

The usual Miller–Rabin test is probabilistic: choose one or more bases, run the test, and report probably prime if all rounds pass. For integers restricted to a known finite range, a different approach is possible. Fixed collections of bases are known that detect every composite number within particular ranges.

That makes Miller–Rabin deterministic within the proven range. The range is part of the guarantee. Copying a fixed base list without its matching upper bound is unsafe because a base set that covers one range does not automatically cover larger integers.

Why modular exponentiation keeps the test practical

The expression a^d mod n can contain an enormous exponent. A program should not construct the full value of a^d and take the remainder afterward. It uses modular exponentiation, usually a square-and-multiply method, so intermediate values are repeatedly reduced modulo n.

The exponent d is processed through its binary representation. As a result, one Miller–Rabin round needs a number of modular squarings and multiplications tied to the bit length of the exponent rather than to the numerical value of the exponent itself.

This is one reason Miller–Rabin scales far better than direct divisor testing for large candidates. Small composites are still cheap to reject first. Implementations commonly handle even numbers and may test divisibility by a collection of small primes before spending time on modular exponentiation.

Miller–Rabin compared with direct prime checking

For smaller integers, a divisor-based result is often easier to inspect directly. The Prime Number Checker is suited to that kind of prime-or-composite check. Miller–Rabin addresses a different computational need: testing much larger candidates without searching through possible divisors up to √n.

Miller–Rabin does not normally factor the number

A failed round proves that the candidate is composite, but the standard test is not a factorization algorithm. The witness may expose a contradiction without producing the prime factors of n.

That difference matters. Primality testing asks whether a number is prime. Factorization asks for the numbers whose product equals the composite input. The first problem can be settled without solving the second.

An enhanced form can perform extra greatest-common-divisor calculations and may return a factor in some failure cases. That is an extension of the basic Miller–Rabin procedure, not a promise that every composite input will be factored.

How Miller–Rabin is used in cryptographic prime generation

Large probable-prime tests appear in public-key cryptography because generating keys can require testing many large odd candidates before suitable primes are found. Miller–Rabin is well matched to this task: an easy composite can be rejected immediately, while repeated rounds can drive the error bound for surviving composites very low.

NIST’s FIPS 186-5 specifies Miller–Rabin procedures for prime generation and validation in RSA-related contexts, including an enhanced version. Its required iteration counts depend on details such as candidate size and the target error probability. Those tables are application-specific; they should not be reduced to a rule such as “two rounds are always enough.”

Where the Miller and Rabin names come from

Gary L. Miller published a primality-testing method in 1976 whose fast deterministic form relied on the Extended Riemann Hypothesis. Michael O. Rabin’s 1980 work turned the underlying idea into an unconditional randomized test with a provable bound on the chance that a composite number survives random testing.

The modern name reflects both steps: Miller supplied the deterministic number-theoretic test structure, while Rabin supplied the randomized form that made the method practical without relying on that unproved hypothesis.

Common Miller–Rabin implementation errors

Skipping the small input cases

The modular test is intended for odd candidates greater than 2. Values below 2, the prime 2 itself, and even numbers greater than 2 should be handled before the main round.

Treating one passing base as a universal proof

A passing randomized base means the candidate is a strong probable prime to that base. A different base may still be a witness.

Using ordinary exponentiation instead of modular exponentiation

Building a^d in full wastes time and memory. The remainder should be maintained during exponentiation.

Copying deterministic bases without their range

A proven base set and its numeric bound form one result. Removing the bound removes the deterministic guarantee.

Confusing the 1/4 theorem with the probability that the candidate is composite

The theorem limits the fraction of liar bases for a composite candidate. It does not say that every one-round probable prime has a one-in-four chance of being composite.

Ignoring arithmetic overflow

In fixed-width integer code, the multiplication used for x² mod n can overflow before the modulus is applied. Large-integer arithmetic, wider intermediate types, or overflow-safe modular multiplication may be needed.

Reusing bases carelessly in a randomized test

The usual repeated-round probability bound assumes suitably selected independent bases. Running the same base again adds no new information.

Reading a Miller–Rabin result correctly

Miller–Rabin works because primes impose a strict shape on the sequence from a^d to aⁿ⁻¹. The test does more than ask whether the sequence ends at 1. It checks whether repeated squaring reaches that endpoint in a way compatible with prime modular arithmetic. When the pattern breaks, compositeness is proved. When it survives, more bases can be tested until the required level of assurance—or a deterministic bounded-range guarantee—has been reached.