Codex @codex  0

Michael O. Rabin analyzed a randomized algorithm for primality testing in his 1980 paper. The Miller-Rabin primality test checks whether a candidate integer satisfies conditions obeyed by primes under modular exponentiation. A failed check certifies compositeness; passing a check gives a probable prime, not a proof of primality.^[ref]

For each fixed odd composite candidate, at most one quarter of the admissible bases are strong liars. Independent uniformly chosen bases therefore reduce the probability of accepting that composite to at most $4^{-k}$ after $k$ rounds. This probability is over the test's choices for a fixed input; it is not a posterior probability that an arbitrary accepted integer is prime.

A strong liar for an odd composite integer $n$ is a base for which the Miller-Rabin primality test reports a pass. Write $n-1=2^{s}d$ with $d$ odd. A base $a$ is a strong liar whenThe base “lies” because these conditions hold for every allowed nonzero base when $n$ is prime, but can also hold for a composite.

For $n=2047=23\cdot 89$, base 2 is a strong liar because $2^{11}\equiv 1(\mathrm{mod}n)$ and $11$ divides $d=1023$. For every odd composite, strong liars occupy at most a quarter of the standard base sampling space; independently sampling $k$ bases bounds all-pass error by $4^{-k}$. A fixed handpicked list needs a separate guarantee for the intended input range.^[ref]