= Strong liar
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> when
$$
a^d\equiv1\pmod n\quad\text{or}\quad a^{2^r d}\equiv-1\pmod n\text{ for some }0\le r<s.
$$
The 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\cdot89$, base 2 is a <strong liar> because $2^{11}\equiv1\pmod 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.<Probabilistic Algorithm for Testing Primality by Michael O. Rabin>[§§1–2, strong-pseudoprime condition and quarter bound]{ref}
Back to article page
