Miller-Rabin prime test

The Miller-Rabin prime test is a probabilistic test based on the following

Theorem 1.

Let $N\mathrm{\ge }\mathrm{3}$ be an odd number and $N\mathrm{-}\mathrm{1}\mathrm{=}{\mathrm{2}}^t\mathit{}n$, $n$ odd. If and only if for every $a\mathrm{\in }\mathrm{Z}$ with $\gcd \mathit{}\mathrm{(}a\mathrm{,}N\mathrm{)}\mathrm{=}\mathrm{1}$ we have

$$a^n\equiv 1\mathit{\hspace{1em}}\mathit{\text{mod }}N\mathit{\hspace{1em}\hspace{1em}}\text{𝑜𝑟}$$(1a)

$$a^{2^{s}n}\equiv -1\mathit{\hspace{1em}}\mathit{\text{mod }}N$$(1b)

for some $s\mathrm{\in }\mathrm{\{}\mathrm{0}\mathrm{,}\mathrm{\dots }\mathrm{,}t\mathrm{-}\mathrm{1}\mathrm{\}}$, then $N$ is prime. If $N$ is not prime, then let $A$ be the set of all $a$ satisfying the above conditions. We have

$$\text{𝐶𝑎𝑟𝑑}(A)\le \frac{1}{4}\phi (N),$$

where $\phi$ is Euler’s Phi-function.

A composite number $N$ satisfying conditions (1) for some $a\in \mathbb{Z}$ is called a strong in the basis $a$. Note that this theorem states that there are no such things as Carmichael numbers for strong pseudoprimes (i.e. composite numbers that are strong pseudoprimes for all values of $a$).From this theorem we can construct the following algorithm:

1. Choose a random $2\le a\le N-1$.

2. If $\gcd (a,N)\ne 1$, we have a non-trivial divisor of $N$, so $N$ is not prime.

3. If $\gcd (a,N)=1$, check if the conditions (1) are satisfied. If not, $N$ is not prime, otherwise the probability that $N$ is not prime is less than $\frac{1}{4}$.

In general the probability, that the test falsely reports $N$ as a prime is far less than $\frac{1}{4}$. Of course the algorithm can be applied several times in order to reduce the probability, that $N$ is not a prime but reported as one.

When comparing this test with the related Solovay-Strassen test one sees that this test is superior is several ways:

• There is no need to calculate the Jacobi symbol.

• The amount of false witnesses, i.e. numbers $a$ that report $N$ as a prime when it is not, is at most $\frac{N}{4}$ instead of $\frac{N}{2}$.

• One can even show that $N$ which passes Miller-Rabin for some $a$ also passes Solovay-Strassen for that $a$, so Miller-Rabin is always better.

Note that when the test returns that $N$ is composite, then this is indeed the case, so it is really a compositeness test rather than a test for primality.