= Deterministic Miller-Rabin primality test
{title2=$n<2^{64}$}
A <deterministic Miller-Rabin primality test> chooses bases justified to distinguish every composite in a specified input range, instead of sampling bases for a probabilistic guarantee. For each base, write $n-1=2^sd$ with odd $d$, test $a^d\bmod n$, and square successively according to the <Miller-Rabin primality test>. A failing base certifies compositeness; passing a fixed list certifies primality only under the proven range theorem for that list. For machine <integers> such as $n<2^{64}$, established finite-range base <sets> permit deterministic implementations. The exact bases, bound, treatment of small primes and modular-arithmetic overflow are part of the <algorithm>'s contract.
Back to article page
