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 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]