Two Primality Testing Algorithms

•  Mar 2020

•  5-minute read

•  Academic Commentaries

---

In this post, two primality tests are described. The first test, the Fermat test, is efficient, but it can only differentiate between given numbers that are either composite or "very probably prime".

The second test, the Miller-Rabin test, is similar to the Fermat test in that it is efficient and probabilistic. It addresses some of the limitations of the Fermat test, but it is still really a test for compositeness rather than a test for primality.

Fermat Primality Test

The key ingredient for this primality test is Fermat's little theorem. This theorem states that an integer \(n\) is prime if and only if, \(\forall x \in \{0, 1, ..., n\}\), the following congruence holds: $$x^{n - 1} \equiv 1 \pmod{n}.$$

This points the way towards a primality test. In particular, we can randomly choose an integer \(a \in \{1, 2, ..., n - 1\}\) (known as a base), and check whether \(a^{n - 1}\) is congruent with \(1 \pmod{n}\).

If the base \(a\) doesn't yield a value of \(a^{n - 1}\) that is congruent with \(1 \pmod{n}\), then we can say that \(a\) is a Fermat witness for the compositeness of \(n\). Hence, we conclude that \(n\) is probably composite.

Else, \(n\) is very probably prime.

In both cases, we need to say probably because the Fermat test cannot distinguish between prime numbers and Carmichael numbers. There are infinitely many Carmichael numbers (e.g., 10585, 62745, 75361).

Also, there is a chance that any Fermat witness to the compositeness of a given input may be a false one. For this reason, some implementations of probabilistic primality test algorithms (including the ones on this page) use specific sets of bases.

Miller-Rabin Primality Test

Like the Fermat test, the Rabin-Miller test involves choosing a base \(a \in \{1, 2, ..., n - 1\}\), and using it to try find a Fermat witness (i.e., an \(a\) such that \(a^{n - 1} \not\equiv 1 \pmod{n}\)). However, this test also checks for fake square roots of \(1 \pmod{n}\), allowing it to distinguish between primes and Carmichael numbers.

The test relies on two theorems, proofs for which are given here.

Theorem 1: Suppose \(p\) is an odd prime. Let \(p - 1 = 2^km\), where \(m\) is odd and \(1 \leq a \lt p\). Then one of the following holds:

• \(a^m \equiv 1 \pmod p\) or
• One of \(a^m, a^{2m}, a^{4m}, a^{3m}, ..., a^{2^{k - 1}m}\) is congruent to \(-1 \pmod{p}\).

Theorem 2: If \(n \in Z \) is composite, then a minimum of 75% of integers \(1 \lt a \lt n\) are witnesses to the compositeness of \(n\).

Hence, the Rabin-Miller algorithm goes as follows:

• Factor \(n - 1\) as \(2^km\), where \(m\) is odd.
• Choose \(a \in \{1, 2, ..., n - 1\}\) at random, potentially several.
• For all chosen \(a\), test whether the statements in Theorem 1 hold.
• If some \(a\) is a witness to the compositeness of \(n\), then \(n\) is definitely composite.
• Else, \(p\) is probably prime.

Implementations

Implementations of the two primality tests described in this post are available all over the Internet. For example, this website uses Python and Django to allow you to run the Fermat and Miller-Rabin tests in your browser. The source code is available at GitHub.