The Miller-Rabin primality test relies on a condition $W_n(b) \implies n$ is composite, and this paper gives a somewhat hefty proof of why the algorithm bears at most $\frac{1}{4}$ false witnesses $b$ to the primality of $n$, i.e. that $\frac{|\{b | W_n(b)\}|}{(n-1)} \geqslant \frac{3}{4}$. Does anyone know of perhaps a simpler proof or some background from which I can more accessibly approach the proof?

Thanks in advance.

  • $\begingroup$ An elementary analysis of this happens on page 3 of Jerry Shurman's notes $\endgroup$
    – Mark
    Dec 19, 2016 at 8:09


You must log in to answer this question.

Browse other questions tagged .