The site's fourth Number Theory entry, and it closes a forward reference from Sieve of Eratosthenes. The sieve finds every prime up to a bound n in one sweep — but that's a different problem from deciding whether one specific, possibly huge, number is prime. Trial division (or a sieve) against a candidate with hundreds of digits doesn't scale: RSA key generation needs to know whether a randomly chosen 300-digit odd number is prime, and √n for a 300-digit n is itself a number with roughly 150 digits — checking that many candidate divisors is computationally hopeless. Miller–Rabin decides primality of one number at a time, fast, at the cost of a small, quantifiable chance of being wrong.
Gary Miller described a deterministic version in 1976, but it relies on an unproven conjecture (the Extended Riemann Hypothesis). Michael Rabin turned it into an unconditional, randomized algorithm in 1980 by picking witnesses at random instead of from a fixed set. Both build on much older ground: Fermat's Little Theorem, from the 1640s.
Fermat's Little Theorem: if p is prime and a is not a multiple of
p, then a^(p-1) ≡ 1 (mod p). That suggests an obvious primality test — pick a base
a, compute a^(n-1) mod n, and if it isn't 1, n is definitely composite
(the contrapositive is airtight). If it is 1, call n "probably prime" and move on.
This almost works, and it's tempting to stop there. It fails outright on Carmichael numbers: composite numbers that pass the Fermat test for every base coprime to them, not just some. 561 = 3 × 11 × 17 is the smallest one — no amount of re-rolling the base rescues the plain Fermat test on a Carmichael number, because there is no base among the coprime ones left to try that would expose it (checked directly in Pitfalls below). The test needs a genuinely different idea, not just more bases.
Enter a number and one or more witness bases (comma-separated), then step through each witness in turn. 2047 with witness 2 shows the classic failure case passing when it shouldn't; adding witness 3 catches it. 561 with witness 2 shows Miller–Rabin correctly exposing the Carmichael number that fools Fermat's test for every base. 97 with witness 5 is a genuine prime, useful for comparing against the off-by-one bug below.
The trick is a second fact that plain Fermat doesn't use: the only square roots of 1 modulo a
prime are 1 and −1. (Modulo a composite, there can be others — that extra freedom is exactly what
lets composite numbers slip past.) Write n − 1 = 2^s · d with d odd (every even
number factors this way). Then the sequence
a^d, a^(2d), a^(4d), ..., a^(2^s · d) = a^(n-1) (mod n)is built by repeated squaring — each term is the previous one, squared. If n is prime,
Fermat's Little Theorem guarantees the last term is 1. Walk the sequence backwards from that final 1: the
term right before the first 1 must itself be a square root of 1 modulo n — and since
n is prime, that means it has to be 1 or −1. If it's 1, keep walking backward through the same
argument. Eventually either the very first term (a^d) is 1, or somewhere along the way a term
is exactly −1 (≡ n−1). There's no third option for a genuine prime.
So the test for a witness a: compute a^d mod n. If it's 1, a
can't disprove primality — pass. Otherwise, repeatedly square it up to s − 1 more times,
checking after each squaring for n − 1. If that ever appears, pass. If the loop runs out
without ever hitting 1 or n − 1, the sequence violates the argument above — impossible for a
prime — so n is definitely composite, and a is called a witness
to that. A composite number can still fool one particular witness (that's the 2047/base-2 case below), but
Rabin proved that for any composite n, at most 1/4 of the bases in [1, n−1] are
false witnesses — so k independent random bases fail to catch a composite with probability at
most 4^-k, dropping below one in a million after 10 rounds.
The modPow helper below computes that repeated-squaring chain — see
Modular Exponentiation for a full, step-through
walkthrough of exactly how it stays fast and small even when n has hundreds of digits.
function modPow(base, exp, mod) { // fast exponentiation, all BigInt
base %= mod;
let result = 1n;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
function isProbablePrime(nValue, witnesses) {
const n = BigInt(nValue);
if (n < 2n) return false;
if (n === 2n) return true;
if (n % 2n === 0n) return false;
let d = n - 1n, s = 0n;
while (d % 2n === 0n) { d /= 2n; s += 1n; } // n - 1 = 2^s * d
for (const raw of witnesses) {
const a = BigInt(raw) % n;
if (a === 0n) continue; // not a useful witness
let x = modPow(a, d, n);
if (x === 1n || x === n - 1n) continue; // this witness passes
let composite = true;
for (let r = 1n; r < s; r++) {
x = (x * x) % n;
if (x === n - 1n) { composite = false; break; }
}
if (composite) return false; // proven composite
}
return true; // probably prime
}A composite number can genuinely fool a single witness — that's not a bug, it's the algorithm's
known, quantified trade-off. 2047 = 23 × 89 is the smallest strong pseudoprime to base 2: computing
its chain with a = 2 gives a^d mod n = a^1023 mod 2047 = 1 directly, so witness 2
passes immediately and reports "probably prime" for a number that plainly isn't. This is checked, not just
claimed — it's exactly what the demo above shows with the first preset. Witness 3 doesn't have this problem:
3^1023 mod 2047 = 1565, then squaring gives 1013, and neither is 1 or 2046, so
witness 3 correctly proves 2047 composite. This is why real implementations use several witnesses, not one —
known results (Pomerance, Selfridge, and Wagstaff) give fixed small witness sets that are provably exact
(not just probable) below specific bounds, e.g. bases {2, 3, 5, 7} are correct for every n below
3,215,031,751. The shipped isProbablePrime above was checked against plain trial division for
every n from 2 to 300,000 using exactly those four bases — zero mismatches.
Fermat's test alone can't be patched by adding more bases — Carmichael numbers fool
all of them. 561 = 3 × 11 × 17 passes the naive Fermat test (a^560 mod 561 = 1)
for every base checked: 2, 5, 7, 10, and 13 all come back 1. No amount of re-rolling the base finds a
counterexample, because none exists among the bases coprime to 561 — this is what "Carmichael number" means.
Miller–Rabin's extra squaring step catches it anyway: with witness 2, the chain is
263, 166, 67, 1, 1 — note the 1 at position four is reached without ever passing through
560 first, which is only possible if 561 is composite, per the square-roots-of-1 argument above. The
demo's second preset shows this chain forming step by step.
An off-by-one in the squaring loop's bound silently rejects real primes. The loop must
run for r from 1 to s − 1 — that's s − 1 squarings after the initial
check, matching the length of the mathematical chain above. Writing the bound as r < s - 1
instead of r < s cuts the very last squaring, and for some (witness, prime) pairs that last
squaring is the only one that ever reaches n − 1. Checked concretely: n = 97 (genuinely prime),
witness 5, has s = 5. The chain is 28, 8, 64, 22, 96 — 96 is n − 1,
and it only appears at the fifth and final position. The correct loop (r < s, four
iterations) reaches it and passes. The buggy loop (r < s - 1, three iterations) stops one
short, never sees 96, and wrongly reports 97 as composite — a false negative on an actual prime, which a
correct implementation of this test should never produce.
O(k log³ n) bit operations for k witnesses against an n-bit number, using
schoolbook multiplication: each witness costs O(log n) modular squarings (fast exponentiation), each
squaring multiplies two O(log n)-bit numbers at O(log² n) cost. That's polynomial in the number of
digits of n, not in n itself — the property that makes it usable on numbers with hundreds of digits,
where trial division's O(√n) cost is astronomically larger (for a 300-digit n, √n itself has roughly 150
digits — utterly infeasible to enumerate). Real cryptographic libraries add a cheap trial-division pre-filter
by small primes before paying for a single modular exponentiation, since most random odd candidates are
ruled out instantly that way — an optimization, not a correctness requirement, so it's left out of the
reference implementation above to keep the core algorithm visible.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.