Tag Archives: primes

Effectiveness of the Miller-Rabin primality test

Last time, I explained the Miller-Rabin probabilistic primality test. Let's recall it: Theorem. Let $p$ be an odd prime and write $p-1 = 2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following statements is true: $a^q\equiv 1\pmod{p}$, or One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k-1}q}$ is congruent […]