= Michael O. Rabin
{c}
<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 <composite number>[compositeness]; passing a check gives a <probable prime>, not a proof of primality.<Probabilistic Algorithm for Testing Primality by Michael O. Rabin>[§§1–2]{ref}
For each fixed odd <composite number>[composite] candidate, at most one quarter of the admissible bases are <strong liar>[strong liars]. <independence>[Independent] uniformly chosen bases therefore reduce the <probability> of accepting that <composite number>[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>.
Back to article page
