Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 37 Β· Primality and Factoring

The Miller-Rabin Primality Test

Learn why Miller-Rabin beats the Fermat test, how strong witnesses work, which fixed bases make it deterministic, and how to generate large primes.

The Fermat test has one fatal flaw: Carmichael numbers fool it for every coprime base. The Miller-Rabin test closes that hole with one extra observation. In the integers modulo a prime, the only square roots of 1 are 1 and -1. If a base reveals a different square root of 1, the modulus cannot be prime.

Miller-Rabin is the workhorse behind sympy.isprime, OpenSSL's prime generation and most big-number libraries. Every composite has at least 3/4 of its bases as strong witnesses, so a handful of rounds gives overwhelming confidence. For numbers below about 3.3 Γ— 10²⁴, a fixed list of bases makes the test fully deterministic.

The idea

Let n be odd and write n - 1 = 2^s Β· d with d odd. If n is prime, then for any base a, the sequence

a^d, a^(2d), a^(4d), ..., a^(2^s Β· d) = a^(n-1) (all mod n)

must either start with 1 or contain -1 (that is, n - 1) somewhere before the end. Why? The last term is 1 by Fermat. Walk backward: each term is the square root of the next one, and the only square roots of 1 are Β±1. So the first term is 1, or we hit -1 before reaching 1.

If a base a shows neither pattern, then a is a strong witness and n is composite. If it shows one of them, n is a strong probable prime to base a.

Python Splitting n-1 and checking the chain

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 97 = 2^5 Β· 3 + 1, the chain for base 5 reaches 96 (that is -1) and then 1. For 561 = 2^4 Β· 35 + 1, base 2 produces a chain that reaches 1 without passing through 560: the value 67 squares to 1 (67Β² = 4489 = 8 Β· 561 + 1), a nontrivial square root of 1 (something other than Β±1). That proves 561 composite, which Fermat could not do.

The algorithm

Python Miller-Rabin from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The function miller_rabin first removes small prime factors, then runs the strong test for each base. The last line confirms that our version agrees with SymPy for all numbers below 100000. The number 3215031751 is interesting: it is the smallest composite that passes the strong test for bases 2, 3, 5 and 7, so you need more bases to catch it.

How many bases do you need?

Rabin proved that for odd composite n, at most a quarter of the bases in [2, n-2] are strong liars. With k independent random bases the error probability is at most 4^-k, and in practice far smaller. Twenty rounds already give an error below 10⁻¹².

For bounded inputs, specific base sets are known to be deterministic:

Limit Bases that suffice
n < 2,047 2
n < 1,373,653 2, 3
n < 3,215,031,751 2, 3, 5, 7
n < 3,317,044,064,679,887,385,961,981 first 13 primes (2 to 41)
n < 2⁢⁴ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
Python Strong liars and the 1/4 bound

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see that the worst fraction is well under 0.25, and that 2047 = 23 Γ— 89 is the smallest composite for which base 2 is a strong liar (the last line prints True).

Generating a large prime

To make a random 512-bit prime, draw random odd 512-bit integers until one passes the test. By the prime number theorem about one in ln(2^512) β‰ˆ 355 numbers is prime, roughly one in 177 odd numbers.

Python Random prime generator

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The final count should be near 2000 Β· 2/ln(2⁢⁴) β‰ˆ 90 (the seeded run above gives 80). This is the same loop that RSA key generation uses, and we will rely on it in RSA from scratch.

flowchart TD
    A["n odd, write n-1 = 2^s * d"] --> B["x = a^d mod n"]
    B --> C{"x is 1 or n-1?"}
    C -->|yes| P["passes for this base"]
    C -->|no| D["square x up to s-1 times"]
    D --> E{"x becomes n-1?"}
    E -->|yes| P
    E -->|no| F["composite"]

One round of Miller-Rabin for a single base a.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. Which fact about primes does Miller-Rabin add to Fermat's test?

    A different square root of 1 proves the modulus is composite, which catches Carmichael numbers.
  2. 2. For an odd composite n, what is the largest share of bases that can be strong liars?

    Rabin's theorem bounds the strong liars by one quarter of the bases, so k rounds fail with probability at most 4^-k.
  3. 3. n - 1 = 2^s * d with d odd. For n = 97 what are s and d?

    96 = 32 * 3 = 2^5 * 3.
  4. 4. Which statement is true?

    A failure produces a witness, which is a proof of compositeness. A pass is only evidence unless you use a known deterministic base set.

Summary

  • Write n - 1 = 2^s Β· d, compute a^d and square up to s - 1 times.
  • A chain that never starts at 1 or hits n - 1 proves n composite.
  • At most 1/4 of the bases lie, so k random rounds give error at most 4^-k.
  • Fixed small base sets make the test deterministic below 2⁢⁴.
  • Random prime search plus Miller-Rabin is how big primes are generated.

Next: Pollard's Rho Factoring