# Effectiveness of the Miller-Rabin primality test

Posted by Jason Polak on 11. May 2018 · Write a comment · Categories: number-theory · Tags:

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:

1. $a^q\equiv 1\pmod{p}$, or
2. One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k-1}q}$ is congruent to $-1$ modulo $p$.

The Miller-Rabin randomized test looks for values of $a$ that don't satisfy the conclusions of this theorem. Such an $a$ is called a witness. If such an $a$ can be found, then $n$ is composite. If no such $a$ is found after a bunch of iterations, then we consider $n$ to be probably prime.

For example, a hundred iterations of Miller-Rabin selected

as a number that is most likely prime. A brute-force factor testing to make sure that this number is prime would take many times the age of the universe. That's pretty crazy! The Miller-Rabin test only takes a couple seconds, but how good is it really?

Now what about the percentage of witnesses for different numbers? Is this percentage close to 75%? In fact, although at least 75% of all possible bases are witnesses for any given composite number, often there are far more bases. In fact, only 0.6% of composite integers below 2000 have fewer than 90% of the total possible bases as witnesses. One such number is 1891 = 31*61. About 76% of possible bases are Miller-Rabin witnesses for 1891, which shows that the estimate of 75% is pretty good.

But for cryptographic applications, we're not interested in finding composite numbers. Given a randomly selected odd composite number, we can say that the probability of the Miller-Rabin test failing to find it composite after $k$ iterations is at most $4^{-k}$, which we can make very small very quickly. However, this conditional probability isn't the same thing as the conditional probability that a randomly selected odd number is composite given that $k$-iterations of Miller-Rabin thinks it is a prime!

A priori, it may be possible that the probability a number is composite given that $k$-iterations of Miller-Rabin thinks it's a prime is higher than $4^{-k}$.

But this isn't the case. Beauchemin, Brassard, Crépeau, Goutier, and Pomerance showed in a paper that this probability (that a randomly selected odd number is composite given $k$-iterations of Miller-Rabin thinks it is a prime) is also at most $4^{-k}$, assuming that the randomly selected odd numbers of sufficiently large (which thankfully is less than the typical modern-day cryptographic application).

Let's start out with the oddest prime of all: 2. Get it? But after that, all the odd primes are either of the form $4k + 1$ or $4k + 3$. For fixed $x$, are there more primes less than $x$ of the form $4k + 1$ or the second form $4k + 3$? Let's write $\pi(4k + r,x)$ for the number of primes less than or equal to $x$ of the form $4k + r$. Here is a graph of the difference $\pi(4k+3,x) – \pi(4k+1,x)$:
Pretty neat right? It looks like this difference is wildly erratic, reaching zero after a short while with a bit of a fight and then for a really good long while the primes of the form $4k +3$ win out. So you might be tempeted to think that primes of the form $4k + 3$ become more and more abundant as $x$ increases. That would be wrong. In fact, John E. Littlewood proved that $\pi(4k +3,x)-\pi(4k + 1,x)$ switches sign infinitely often!
Of course, that must mean there are infinitely many primes of both types, and that's true and a special case of Dirichlet's theorem: there are infinitely many primes in any arithmetic progression $ax + b$ whenever $a$ and $b$ are relatively prime.