Primality Tests: Fermat and Miller-Rabin

This article describes two primality tests. The first, the Fermat test, is efficient, but it can only distinguish numbers that are either composite or “very probably prime”.

The second, the Miller-Rabin test, is similar: it is also efficient and probabilistic. It addresses some of the Fermat test’s limitations, but it remains, strictly speaking, a test for compositeness rather than primality.

Fermat Primality Test

The key ingredient here is Fermat’s little theorem. It states that if an integer $n$ is prime, then for every integer $a$ with $1 \le a \le n - 1$ the following congruence holds:

$$a^{n - 1} \equiv 1 \pmod{n}.$$

This points the way towards a primality test. We can pick an integer $a \in \{1, 2, \dots, n - 1\}$ at random (called a base) and check whether $a^{n - 1}$ is congruent to $1 \pmod{n}$.

If the base $a$ does not yield a value of $a^{n - 1}$ that is congruent to $1 \pmod{n}$, then $a$ is a Fermat witness to the compositeness of $n$, and we conclude that $n$ is composite. Otherwise, $n$ is very probably prime.

In both cases we have to say probably, because the Fermat test cannot distinguish prime numbers from Carmichael numbers. There are infinitely many Carmichael numbers (for example, 10585, 62745, and 75361).

There is also a chance that any given Fermat witness is a false one. For this reason, some implementations of probabilistic primality tests use specific, carefully chosen sets of bases.

Miller-Rabin Primality Test

Like the Fermat test, the Miller-Rabin test chooses a base $a \in \{1, 2, \dots, n - 1\}$ and uses it to look for a Fermat witness — that is, an $a$ such that $a^{n - 1} \not\equiv 1 \pmod{n}$. Crucially, it also checks for non-trivial square roots of $1 \pmod{n}$, which lets it distinguish primes from Carmichael numbers.

The test relies on two theorems, with proofs available here.

Theorem 1. Suppose $p$ is an odd prime, and write $p - 1 = 2^k m$ where $m$ is odd. Then for any $a$ with $1 \le a < p$, one of the following holds:

• $a^m \equiv 1 \pmod{p}$, or
• one of $a^m, a^{2m}, a^{4m}, \dots, a^{2^{k - 1} m}$ is congruent to $-1 \pmod{p}$.

Theorem 2. If $n$ is composite, then at least 75% of the integers $a$ with $1 < a < n$ are witnesses to the compositeness of $n$.

The Miller-Rabin algorithm therefore proceeds as follows:

• Factor $n - 1$ as $2^k m$, where $m$ is odd.
• Choose one or more $a \in \{1, 2, \dots, n - 1\}$ at random.
• For each chosen $a$, test whether the conditions in Theorem 1 hold.
• If any $a$ is a witness to the compositeness of $n$, then $n$ is definitely composite.
• Otherwise, $n$ is probably prime.

Implementations

Implementations of both primality tests are available all over the internet, in virtually every programming language. Writing your own is a worthwhile exercise: it forces you to confront the modular-arithmetic details — particularly fast modular exponentiation — that make these tests efficient in practice.