Introduction

Pick any number nn and ask: is it prime? The obvious strategy is trial division — test every number up to n\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 nn is prime, then an−1≡1(modn)a^{n-1} \equiv 1 \pmod{n} for every aa not divisible by nn. If that congruence fails for even one aa, the number is provably composite.

The catch: there are composite numbers that fool Fermat for every aa. 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 an−1≡1a^{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.

Try It: Catch a Fake Prime

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

<p class="hint">Enter a number and a witness <b>a</b> to run both the Fermat test and Miller-Rabin side-by-side. Try <b>n = 561</b> (a Carmichael number) with <b>a = 2</b> — Fermat says "prime", Miller-Rabin says "composite".</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">Run both tests</button>
  <button id="try-561-btn" type="button" class="ghost">Try n = 561</button>
  <button id="try-577-btn" type="button" class="ghost">Try n = 577 (prime)</button>
</div>
<div id="results" class="results hidden">
  <div class="test-block">
    <div class="test-label fermat-label">Fermat Test</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">Miller-Rabin</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; } }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Miller-Rabin demo: compare Fermat test vs Miller-Rabin on the same (n, a).
// Uses BigInt for exact modular arithmetic even for large n.

function modpow(base, exp, mod) {
  base = BigInt(base); exp = BigInt(exp); mod = BigInt(mod);
  if (mod === 1n) return 0n;
  let result = 1n;
  base = base % mod;
  while (exp > 0n) {
    if (exp % 2n === 1n) result = result * base % mod;
    exp = exp / 2n;
    base = base * base % mod;
  }
  return result;
}

// Write n-1 as 2^s * d where d is odd. Returns {s, d}.
function factorOut2(n) {
  n = BigInt(n);
  let s = 0n, d = n - 1n;
  while (d % 2n === 0n) { d /= 2n; s++; }
  return { s, d };
}

// Fermat test: returns true if a^(n-1) ≡ 1 (mod n).
function fermat(n, a) {
  return modpow(a, BigInt(n) - 1n, n) === 1n;
}

// Miller-Rabin witness check.
// Returns {isProbablePrime, steps} where steps is the chain of squarings.
function millerRabinWitness(n, a) {
  const bn = BigInt(n);
  const ba = BigInt(a);
  const { s, d } = factorOut2(bn);
  const steps = [];

  let x = modpow(ba, d, bn);
  steps.push({ power: `a^d`, value: x });

  if (x === 1n || x === bn - 1n) {
    return { isProbablePrime: true, steps, reason: x === 1n ? 'a^d ≡ 1' : 'a^d ≡ −1' };
  }

  for (let r = 1n; r < s; r++) {
    x = x * x % bn;
    steps.push({ power: `a^(2^${r}·d)`, value: x });
    if (x === bn - 1n) {
      return { isProbablePrime: true, steps, reason: `a^(2^${r}·d) ≡ −1` };
    }
    if (x === 1n) {
      return { isProbablePrime: false, steps, reason: `Non-trivial square root of 1 found` };
    }
  }
  // Never reached -1 before 1 (or at end)
  return { isProbablePrime: false, steps, reason: `a^(n−1) did not reach 1 through −1` };
}

// Simple trial division to know truth (only for small n in demo)
function isTrulyPrime(n) {
  n = Number(n);
  if (n < 2) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  for (let i = 3; i * i <= n; i += 2) if (n % i === 0) return false;
  return true;
}

function run() {
  const nVal = parseInt(document.getElementById('n-input').value, 10);
  const aVal = parseInt(document.getElementById('a-input').value, 10);
  const results = document.getElementById('results');
  const explanation = document.getElementById('explanation');

  if (isNaN(nVal) || nVal < 3 || isNaN(aVal) || aVal < 2 || aVal >= nVal) {
    explanation.textContent = 'Please enter n ≥ 3 and 2 ≤ a < n.';
    results.classList.add('hidden');
    return;
  }

  // --- Fermat test ---
  const fermatOk = fermat(nVal, aVal);
  const fermatExp = modpow(aVal, BigInt(nVal) - 1n, BigInt(nVal));
  document.getElementById('fermat-chain').textContent =
    `${aVal}^${nVal - 1} mod ${nVal} = ${fermatExp}`;
  const fermatVerdict = document.getElementById('fermat-verdict');
  if (fermatOk) {
    fermatVerdict.textContent = '✓ Passes — "probably prime"';
    fermatVerdict.className = 'verdict pass';
  } else {
    fermatVerdict.textContent = '✗ Fails — definitely composite';
    fermatVerdict.className = 'verdict fail';
  }

  // --- Miller-Rabin ---
  const { s, d } = factorOut2(BigInt(nVal));
  document.getElementById('mr-decompose').textContent =
    `n-1 = ${nVal - 1} = 2^${s} x ${d}`;
  const { isProbablePrime, steps, reason } = millerRabinWitness(nVal, aVal);
  const chainEl = document.getElementById('mr-chain');
  chainEl.innerHTML = steps.map(st =>
    `<div>${st.power} mod n = ${st.value}</div>`
  ).join('');
  const mrVerdict = document.getElementById('mr-verdict');
  if (isProbablePrime) {
    mrVerdict.textContent = fmt('✓ Passes (%reason%)', { reason: reason });
    mrVerdict.className = 'verdict pass';
  } else {
    mrVerdict.textContent = fmt('✗ Fails — composite! (%reason%)', { reason: reason });
    mrVerdict.className = 'verdict fail';
  }

  results.classList.remove('hidden');

  // --- Explanation ---
  const truly = isTrulyPrime(nVal);
  let msg = '';
  if (truly) {
    msg = fmt('%nVal% is a genuine prime. Both tests pass for every witness — no contradiction possible.', { nVal: nVal });
  } else if (fermatOk && !isProbablePrime) {
    msg = fmt('%nVal% is composite but fools the Fermat test with a = %aVal%. Miller-Rabin catches it: the chain of squarings reveals a non-trivial square root of 1 (impossible in a prime field).', { nVal: nVal, aVal: aVal });
  } else if (fermatOk && isProbablePrime) {
    msg = fmt('%nVal% is composite, and both tests pass with a = %aVal%. Try another witness — for Carmichael numbers like 561, Miller-Rabin still eventually catches them with the right a.', { nVal: nVal, aVal: aVal });
  } else {
    msg = fmt('%nVal% is composite. The Fermat test also fails here with a = %aVal%, so both tests agree.', { nVal: nVal, aVal: aVal });
  }
  explanation.textContent = msg;
}

document.getElementById('run-btn').addEventListener('click', run);
document.getElementById('try-561-btn').addEventListener('click', () => {
  document.getElementById('n-input').value = '561';
  document.getElementById('a-input').value = '2';
  run();
});
document.getElementById('try-577-btn').addEventListener('click', () => {
  document.getElementById('n-input').value = '577';
  document.getElementById('a-input').value = '2';
  run();
});

// Run on load with defaults
run();
Result
Console

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

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

The Real Complexity

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

  • Trial division runs in O(n)O(\sqrt{n}) arithmetic operations — exponential in the number of digits, far too slow for cryptographic inputs.
  • Miller-Rabin runs in O(klog⁡2n)O(k \log^2 n) time with kk random witnesses. Each composite is caught with probability at least 3/43/4 per round, so the chance of a false prime after kk rounds is at most (1/4)k(1/4)^k — astronomically small for k=40k = 40.
  • Under the Generalized Riemann Hypothesis (GRH), Gary Miller showed in 1976 that testing all witnesses a≤2(ln⁡n)2a \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,751n < 3{,}215{,}031{,}751, witnesses {2,3,5,7}\{2, 3, 5, 7\} always suffice; for n<3.3×1024n < 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.

Where It Matters

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 pp and qq. 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+1p = 2q + 1 where both pp and qq 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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/miller-rabin/Content licensed under CC BY-NC 4.0.