Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

How to Learn the Miller–Rabin Primality Test: Modular Exponentiation, Witnesses, Strong Pseudoprimes and Error Bounds

How can a computer test an enormous integer for primality without trying every possible divisor? Miller–Rabin is one of the best algorithms for learning the difference between exhaustive proof and carefully controlled probabilistic evidence. It uses modular arithmetic to ask whether a candidate integer behaves in a way every prime must behave.

This article develops Miller–Rabin from a simple parity observation to professional implementation practice. It complements the broader Number-Theoretic Algorithms article, whose canonical job is the wider number-theory landscape.

Quick Read

Miller–Rabin is a fast primality test based on modular exponentiation.
If a tested base exposes impossible prime-like behaviour, the number is definitely composite.
If the number survives a round, it is a probable prime for that base, not automatically a mathematical proof of primality.
For odd composite integers, a random-base round has a strong worst-case error bound; independent rounds rapidly reduce the chance of a false probable-prime result.
Professional cryptographic software should use vetted libraries and current standards rather than home-made random-base logic.

1. Beginner Level: Why n − 1 Matters

Take an odd integer n > 2. Because n − 1 is even, we can factor out powers of two:

n − 1 = d · 2^s, where d is odd.

For example, if n = 41, then n − 1 = 40 = 5 · 2³. So d = 5 and s = 3. This decomposition gives Miller–Rabin a sequence of exponents to inspect: d, 2d, 4d, …, 2^sd = n − 1.

The key idea is that prime moduli have tightly constrained square roots of 1. Modulo a prime p, if x² ≡ 1 (mod p), then x ≡ 1 or x ≡ −1. Miller–Rabin uses repeated squaring to look for behaviour that violates this prime structure.

2. The Test, One Round at a Time

Choose a base a with 2 ≤ a ≤ n − 2. Compute x = a^d mod n.

If x = 1 or x = n − 1, this round passes.
Otherwise square x modulo n repeatedly, at most s − 1 times.
If one of those squares becomes n − 1, the round passes.
If n − 1 never appears, a is a witness that n is composite.

This asymmetry is important: finding a witness proves compositeness immediately. Failing to find a witness does not by itself prove primality.

3. Worked Example: n = 21

We know 21 is composite, but let the algorithm discover that. Write 20 = 5 · 2², so d = 5 and s = 2. Choose base a = 2.

Compute 2⁵ mod 21 = 32 mod 21 = 11. This is neither 1 nor 20. We have one squaring step available: 11² mod 21 = 121 mod 21 = 16. We still did not obtain 20. Therefore base 2 is a witness and 21 is composite.

The algorithm did not need to discover the factor 3 or 7. It found a modular contradiction instead.

4. Why Fast Modular Exponentiation Is the Engine

Computing a^d directly would create an enormous intermediate integer. Instead, binary exponentiation repeatedly squares while reducing modulo n. The exponent needs only O(log d) bit decisions.

def pow_mod(base, exponent, modulus):
    result = 1
    base %= modulus
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

Python’s built-in pow(a, d, n) already performs efficient modular exponentiation, so educational code should usually use it after the learner understands what it replaces.

5. Pseudocode

if n < 2: composite
if n is 2 or 3: prime
if n is even: composite

write n - 1 as d * 2^s with d odd

repeat for chosen bases a:
    x = a^d mod n
    if x == 1 or x == n - 1:
        continue to next base

    repeated s - 1 times:
        x = x^2 mod n
        if x == n - 1:
            continue to next base

    return composite

return probable prime

6. A Clear Python Implementation

import random

def miller_rabin(n, rounds=20):
    if n < 2:
        return False
    small_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
    if n in small_primes:
        return True
    for p in small_primes:
        if n % p == 0:
            return False

    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d //= 2

    for _ in range(rounds):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False

    return True

This version is suitable for tracing and experiments, not for generating cryptographic keys. Security-sensitive systems need secure randomness, specified prime-generation procedures, careful parameter choices and reviewed libraries.

7. Witnesses, Liars and Strong Pseudoprimes

For a composite n, some bases may nevertheless make the number pass a Miller–Rabin round. Such a base is often called a strong liar, and a composite that passes for a particular base is a strong pseudoprime to that base. The algorithm becomes powerful because the set of lying bases is limited: for an odd composite n, at most one quarter of eligible bases can be strong liars.

That gives a clean classroom calculation. If independent random bases are used, the worst-case probability of an undetected odd composite is at most (1/4)^k after k rounds. Ten rounds gives a bound below one in a million; twenty rounds pushes it below roughly one in a trillion. Real systems may use deterministic base sets for bounded machine-integer ranges or standards-defined probabilistic procedures for larger values.

8. Why Fermat Testing Is Not Enough

Fermat’s little theorem tells us that for prime p and a not divisible by p, a^p−1 ≡ 1 mod p. A basic Fermat primality test therefore rejects many composites. But Carmichael numbers can satisfy the Fermat congruence for every base coprime to them. Miller–Rabin is stronger because it examines the chain of square roots that leads toward 1, not merely the final exponent.

9. Complexity

Each round performs modular exponentiation plus at most s − 1 modular squarings. Counting arithmetic operations, exponentiation needs O(log n) modular multiplications. Bit complexity depends on the multiplication algorithm used for numbers of the relevant size, so professional performance discussions should distinguish “number of modular multiplications” from machine-level runtime.

The important practical lesson is that Miller–Rabin replaces trial division up to √n with a number of modular arithmetic operations that grows only logarithmically in the exponent length for each round. That difference becomes enormous for large integers.

10. Edge Cases and Failure Modes

Handle n < 2 explicitly.
Recognise 2 and 3 as prime before applying odd-number logic.
Reject even n > 2 immediately.
Do not choose bases outside the intended interval.
Do not confuse “probable prime” with a proof certificate.
Do not use a weak random-number generator in security-sensitive prime generation.
Do not assume a deterministic base set proven for one numeric range remains valid for arbitrary-size integers.
Do not ignore small-prime trial division; it cheaply removes many composites before expensive rounds.

11. Professional Cryptographic Context

NIST’s FIPS 186-5 Digital Signature Standard defines procedures around primes used in approved digital-signature algorithms and distinguishes probable primes from provable primes. The professional lesson is not “implement Miller–Rabin from this article and generate keys.” It is the opposite: understand the test deeply enough to know why standards and mature cryptographic libraries specify prime-generation procedures, randomness requirements and validation steps.

When correctness must be auditable, record whether the system needs a probable-prime result, a deterministic result for a bounded integer domain, or a formal primality certificate. Those are different receiver requirements and should lead to different tools.

12. Learning Progression: Beginner to Professional

Beginner: factor n − 1 into d·2ˢ and trace repeated squaring by hand.
Intermediate: implement modular exponentiation and a single Miller–Rabin round.
Advanced: test Carmichael numbers, count witnesses and explore error bounds empirically.
Professional: study deterministic bounded-range variants, big-integer costs, secure randomness and standards-defined prime generation.

13. Practice Problems

Run one round by hand for n = 25 using bases 2 and 7.
Explain why finding one witness is conclusive but passing one base is not.
Compare trial division and Miller–Rabin on randomly generated 32-, 64-, 256- and 1024-bit odd integers.
Generate Carmichael numbers from a reference list and compare Fermat and Miller–Rabin behaviour.
Instrument your implementation to count modular multiplications rather than only elapsed time.
Research why cryptographic libraries may combine small-prime sieving, probable-prime tests and additional validation.

14. Sources and Further Reading

Final idea: Miller–Rabin teaches an important algorithmic habit: do not ask only whether an answer looks plausible. Ask what structure must be present if the claim is true, then design a test that searches for a contradiction cheaply.