The Miller-Rabin Test

Pick any number $n$ and ask: is it prime? The obvious strategy is trial division — test every number up to $\sqrt{n}$. That works, but it is painfully slow for the 1024-bit numbers used in RSA encryption.

A faster naive test exploits Fermat's Little Theorem: if $n$ is prime, then $a^{n-1} \equiv 1 \pmod{n}$ for every $a$ not divisible by $n$. If that congruence fails for even one $a$, the number is provably composite.

The catch: there are composite numbers that fool Fermat for every $a$. The smallest is 561 = 3 × 11 × 17. These are called Carmichael numbers, and there are infinitely many of them. A pure Fermat test will always call 561 prime — it is wrong every single time.

Miller-Rabin (Gary Miller 1976, Michael Rabin 1980) fixes this by strengthening the condition. Instead of just checking $a^{n-1} \equiv 1$, it also inspects the square roots that appear along the way. This extra check catches Carmichael numbers and, with enough random witnesses, makes an error essentially impossible.

The number 561 passes the Fermat test for every witness — yet it factors as $3 \times 11 \times 17$. Enter any number below and pick a witness $a$ to run both tests side-by-side.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>n = <input id="n-input" type="number" value="561" min="3" step="2"></label>
  <label>a = <input id="a-input" type="number" value="2" min="2"></label>
  <button id="run-btn" type="button">{{btn_run}}</button>
  <button id="try-561-btn" type="button" class="ghost">{{btn_try_561}}</button>
  <button id="try-577-btn" type="button" class="ghost">{{btn_try_577}}</button>
</div>
<div id="results" class="results hidden">
  <div class="test-block">
    <div class="test-label fermat-label">{{label_fermat}}</div>
    <div id="fermat-chain" class="chain"></div>
    <div id="fermat-verdict" class="verdict"></div>
  </div>
  <div class="test-block">
    <div class="test-label mr-label">{{label_mr}}</div>
    <div id="mr-decompose" class="chain"></div>
    <div id="mr-chain" class="chain"></div>
    <div id="mr-verdict" class="verdict"></div>
  </div>
</div>
<div id="explanation" class="explanation"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: 1rem; }
.controls label { display: flex; align-items: center; gap: .3rem; font-weight: 600; }
.controls input { width: 90px; font: 600 15px ui-monospace, monospace; padding: .3rem .4rem;
                  border: 1px solid #adb1b8; border-radius: 6px; text-align: right; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.results { display: grid; grid-template-columns: 1fr 1fr; gap: .8rem; margin-bottom: .8rem; }
.results.hidden { display: none; }
.test-block { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px; padding: .7rem; }
.test-label { font-weight: 700; font-size: .8rem; text-transform: uppercase; letter-spacing: .06em;
              margin-bottom: .5rem; }
.fermat-label { color: #c92f3c; }
.mr-label { color: #0a7d33; }
.chain { font: 14px ui-monospace, monospace; color: #334; margin-bottom: .4rem; line-height: 1.6;
         word-break: break-all; }
.verdict { font-weight: 700; font-size: .95rem; padding: .3rem .5rem; border-radius: 6px; margin-top: .3rem; }
.verdict.pass { background: #d4f0dc; color: #0a7d33; }
.verdict.fail { background: #fce4e6; color: #c92f3c; }
.verdict.prime { background: #e8eef3; color: #1d3557; }
.explanation { background: #fffbe6; border-left: 3px solid #e6b800; border-radius: 0 8px 8px 0;
               padding: .6rem .8rem; font-size: .88rem; line-height: 1.5; }
@media (max-width: 520px) { .results { grid-template-columns: 1fr; } }

// Code not found

Notice the asymmetry. The Fermat test sees $a^{560} \equiv 1 \pmod{561}$ and declares 561 prime — wrong. Miller-Rabin writes $560 = 2^4 \times 35$, then checks the chain of square roots: it finds a value that is neither $1$ nor $-1$ but whose square is $1$, which is impossible for a true prime. Busted.

For a genuine prime like 577, every witness $a$ satisfies both tests. For 561, Miller-Rabin catches it with witness $a = 2$ on the very first try.

How hard is primality testing, really? The complexity story here is unusually rich:

• Trial division runs in $O(\sqrt{n})$ arithmetic operations — exponential in the number of digits, far too slow for cryptographic inputs.
• Miller-Rabin runs in $O(k \log^2 n)$ time with $k$ random witnesses. Each composite is caught with probability at least $3/4$ per round, so the chance of a false prime after $k$ rounds is at most $(1/4)^k$ — astronomically small for $k = 40$.
• Under the Generalized Riemann Hypothesis (GRH), Gary Miller showed in 1976 that testing all witnesses $a \leq 2(\ln n)^2$ suffices to make the test deterministic — no randomness needed. This status is conditional: proven, but only assuming GRH is true.
• PRIMES is in P — unconditionally. In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena published the AKS algorithm, proving that primality can be decided in polynomial time with no randomness and no unproven hypotheses. The result ended a 30-year open question. In practice, AKS is slower than Miller-Rabin, so Miller-Rabin remains the workhorse.
• Deterministic witness sets: for numbers below specific bounds, small fixed witness sets are sufficient. For $n < 3{,}215{,}031{,}751$, witnesses $\{2, 3, 5, 7\}$ always suffice; for $n < 3.3 \times 10^{24}$, 13 witnesses cover all cases. These let implementations be fully deterministic without relying on GRH.

The moral: primality is easier than factoring. We can confirm a number is prime fast, but extracting its factors is believed to be hard — that asymmetry is what makes RSA secure.

Primality testing is not a curiosity — it is infrastructure. Miller-Rabin runs inside virtually every secure system:

• RSA and public-key cryptography: generating an RSA key pair requires finding two large primes $p$ and $q$. A typical key generation loop picks random odd numbers and runs Miller-Rabin until a prime is found — this happens millions of times a day in TLS handshakes.
• Safe prime generation: protocols like Diffie-Hellman benefit from safe primes $p = 2q + 1$ where both $p$ and $q$ are prime. Miller-Rabin is used to test both.
• Elliptic-curve cryptography: curve parameters often require finding primes with specific properties; Miller-Rabin is part of the construction pipeline.
• Blockchain and hash functions: proof-of-work schemes and some consensus mechanisms rely on large primes; Miller-Rabin is the standard primality check.
• Teaching randomized algorithms: Miller-Rabin is a textbook example of a Monte Carlo algorithm — it can be wrong, but the error probability is under our control. It sits alongside probabilistic data structures as a gateway to understanding randomized computation.

Every time you visit an HTTPS website, Miller-Rabin has almost certainly run in the background — catching fake primes so your connection stays secure.

The Miller-Rabin test is a lesson in how a small extra check can turn a broken algorithm into a reliable one. Fermat's test is elegant but fatally fooled by Carmichael numbers; Miller-Rabin adds one step — inspect the square roots — and suddenly every composite number can be caught.

The story does not end there. The AKS breakthrough of 2002 showed that primality sits firmly in P — it is not just probably easy, it is provably easy. Yet Miller-Rabin remains the practical choice because its probabilistic version is faster in every real-world scenario.

So the next time you open a secure website, remember: buried in that TLS handshake is a number-theoretic card trick. Some random witnesses, a chain of square roots, and the certainty that whatever primes secured your session are the real thing — not impostors hiding behind Fermat's theorem.