MAT 3343, APPLIED ALGEBRA, FALL 2003

Handout 4: The Miller-Rabin Primality Test

Peter Selinger

1 Fermat Pseudoprimes

A primality test is an algorithm which, given an integer n, decides whether n is prime or not. The most naive algorithm, trial division, is hopelessly inefficient when n is very large. Fortunately, there exist much more efficient algorithms for determining whether n is prime. The most common such algorithms are probabilistic; they give the correct answer with very high probability. All efficient primality testing algorithms are based, in one way or another, on Fermat’s Little Theorem.

Theorem 1.1 (Fermat). If p is prime, then for all b ∈ {1, …, p − 1},

b^{p−1} ≡ 1(mod p).

Definition (Fermat pseudoprime). Let n ⩾ 2 and b ∈ {1, …, n − 1}. We say that the number n passes the Fermat pseudoprime test at base b if b^{n−1} ≡ 1(mod n). A number n is called a Fermat pseudoprime if it passes the Fermat pseudoprime test for all b ∈ ℤ_{n}^{∗}.

By Fermat’s Little Theorem, every prime number is a Fermat pseudoprime. Unfortunately, the converse does not hold. There are Fermat pseudoprimes which are not prime. Such numbers are called Carmichael numbers. The first few Carmichael numbers are

561, 1105, 1729, …

Nevertheless, the notion of a Fermat pseudoprime is a useful notion, not least because there is a very efficient probabilistic algorithm for checking whether a given number n is a Fermat pseudoprime.

Proposition 1.2. If n is not a Fermat pseudoprime, then n fails the Fermat pseudoprime test at base b for at least half of the elements b ∈ {1, …, n − 1}.

Proof. Suppose n is not a Fermat pseudoprime, and let

G = {b ∈ ℤ_{n} | b^{n−1} ≡ 1(mod n)} ⊆ ℤ_{n}^{∗}.

Then G is a subgroup of ℤ_{n}^{∗}, thus |G| ⩽ |ℤ_{n}^{∗}|. Since n is not a Fermat pseudoprime, there exists some b ∈ ℤ_{n}^{∗} with b ∉ G, thus |G| < |ℤ_{n}^{∗}|. It follows that |G| ⩽ \frac{1}{2}|ℤ_{n}^{∗}| ⩽ \frac{n−1}{2}. Finally, whenever b ∈ \{1, …, n − 1\} and b ∉ G, then b fails the test; there are at least \frac{n−1}{2} such elements.

Algorithm 1.3 (Fermat pseudoprime test).

Input: Integers n ⩾ 2 and t ⩾ 1.

Output: If n is prime, output “yes”. If n is not a Fermat pseudoprime, output “no” with probability at least 1 − 1/2^{t}, “yes” with probability at most 1/2^{t}.

Algorithm: Pick t independent, uniformly distributed random numbers b_{1}, …, b_{t} ∈ {1, …, n − 1}. If b_{i}^{n−1} ≡ 1(mod n) for all i, output “yes”, else output “no”.

Proof. We prove that the output of the algorithm is as specified. If n is prime, then the algorithm outputs “yes” by Fermat’s Little Theorem. If n is not a Fermat pseudoprime, then by Proposition 1.2, n passes the test at base b_{i} with probability at most \frac{1}{2}. Hence the probability that n passes all t tests is at most 1/2^{t}. □

Algorithm 1.3 can distinguish prime numbers from non-Fermat-pseudoprimes. We did not specify its behavior if the input is a Carmichael number. As a matter of fact, if the input is a Carmichael number, the algorithm will usually output “yes”, but will output “no” with a small probability (namely, when n has a common prime factor with one of the b_{i}).

2 Carmichael numbers

Before describing an improved version of the primality testing algorithm, we prove some useful properties of Carmichael numbers, i.e., non-prime Fermat pseudoprimes.

Lemma 2.1. Let p^{e} be a prime power with e ⩾ 2. Then the group ℤ_{p^{e}}^{∗} has an element of order p.

Proof. Consider G = {1 + p^{e−1}x | x ∈ ℤ_{p_{e}}}. Clearly G is a subgroup of ℤ_{p^{e}}^{∗} with p elements. Since p is prime, each element g ∈ G has order 1 or p. The only element of G of order 1 is 1, hence e.g. g = 1 + p^{e−1} has order p. □

Proposition 2.2. Let n be a Carmichael number. Then n is odd, and we can factor n = m_{1}m_{2}, where m_{1}, m_{2} ⩾ 3 and gcd(m_{1}, m_{2}) = 1.

Proof. To show that n is odd, assume on the contrary that it is even. Then n ⩾ 4, since 2 is not a Carmichael number. Moveover, n − 1 is odd, so we have (−1)^{n−1} ≡ −1(mod n). It follows that n fails the Fermat pseudoprime test at base b = −1.

To show that n has the desired factorization, it suffices to show that two distinct primes occur in the prime factorization of n. Since n is not itself prime, this is equivalent to proving that n is not of the form p^{e}, for some prime p and e ⩾ 2. Suppose, for contradiction, that n = p^{e}. Then, by Lemma 2.1, there is an element x ∈ ℤ_{n}^{∗} of order p. Since n is a Fermat pseudoprime, we also have x^{n−1} ≡ 1(mod n), hence p|n − 1. But this is impossible since p|n. □

3 Strong Pseudoprimes

Definition (Strong pseudoprime). Let n be odd and write n − 1 = 2^{s}l, where l is odd. Given b, compute the following elements of ℤ_{n}:

b^{l}, b^{2l}, b^{4l}, …, b^{2^{s−1}l}, b^{2^{s}l} = b^{n−1}.

We say that n passes the strong pseudoprime test at base b if either b^{l} ≡ 1(mod n) or b^{2^{r}l} ≡ −1(mod n) for some 0 ⩽ r < s.

Note that in the sequence b^{l}, b^{2l}, b^{4l}, …, b^{2^{s−1}l}, b^{2^{s}l}, each element is the square of the preceding element. Thus if one of these elements is 1 or −1, then all the following elements are equal to 1.

Remark 3.1. If n passes the strong pseudoprime test at base b, then it also passes the Fermat pseudoprime test at base b. In particular, any strong pseudoprime is a Fermat pseudoprime. Proof: If n passes the strong pseudoprime test at b, then either b^{l} ≡ 1(mod n) or b^{2^{r}l} ≡ −1(mod n) for some r < s. In either case, b^{2^{s}l} ≡ 1(mod n), and hence b^{n−1} ≡ 1(mod n).

Remark 3.2. Any prime is a strong pseudoprime. Proof: If n is prime, then ℤ_{n} is a field. It follows that the polynomial x^{2} − 1 has at most two roots in ℤ_{n}. These roots are ±1. By Fermat’s Little Theorem, b^{2^{s}l} = b^{n−1} = 1(mod n). If b^{l} ≠ 1(mod n), then let r be maximal such that b^{2^{r}l} ≠ 1. Then (b^{2^{r}l})^{2} = 1 implies b^{2^{r}l} = −1, so n passes the test at b.

Proposition 3.3. If n is not prime, then n fails the strong pseudoprime test at base b for at least half of the elements b ∈ {1, …, n − 1}.

Proof. Let n − 1 = 2^{s}l as before. If n is not a Fermat pseudoprime, then the result follows from Proposition 1.2 and Remark 3.1. So let us consider the case where n is a Carmichael number. By Proposition 2.2, we can write n = m_{1}m_{2}, where m_{1}, m_{2} ⩾ 3 and gcd(m_{1}, m_{2}) = 1. Since l is odd, we have (−1)^{l} ≢ 1(mod n). Let r be the maximal integer such that there exists some b ∈ ℤ_{n}^{∗} with b^{2^{r}l} ≢ 1(mod n). Note that 0 ⩽ r < s. Let

G = {b ∈ ℤ_{n}^{∗} | b^{2^{r}l} ≡ ±1(mod n)}.

Clearly, G is a subgroup of ℤ_{n}^{∗}, hence |G| divides |Z_{n}^{∗}|. We now show that G is a strict subset of ℤ_{n}^{∗}. By definition of r, there exists some b ∈ ℤ_{n}^{∗} with b^{2^{r}l} ≢ 1(mod n). Then either b ∉ G, or else b^{2^{r}l} ≡ −1(mod n). In the latter case, use the Chinese Remainder Theorem to define b′ ∈ ℤ_{n}^{∗} such that b′ ≡ b(mod m_{1}) and b′ ≡ 1(mod m_{2}). Then b′^{2^{r}l} ≡ −1(mod m_{1}) and b′^{2^{r}l} ≡ 1(mod m_{2}). This implies b′^{2^{r}l} ≢ ±1(mod n), hence b′ ∉ G. In either case, G ≠ ℤ_{n}^{∗}. Thus, |G| < |ℤ_{n}^{∗}|, hence |G| ⩽ \frac{1}{2}|ℤ_{n}^{∗}| ⩽ \frac{n−1}{2}.

Finally, we claim that for all b ∈ {1, …, n − 1} with b ∉ G, n fails the strong pseudoprime test at base b. Indeed, either b is not a unit, in which case b^{n−1} ≢ 1(mod n). Or else, b^{2^{r+1}l} ≡ 1(mod n) but b^{2^{r}l} ≢ ±1(mod n), causing the test to fail. As there are at least \frac{n−1}{2} elements in \{1, …, n − 1\} \ G, we are done. □

As a result of Remark 3.2 and Proposition 3.3, we obtain an efficient probabilistic algorithm for primality testing. This algorithm is known as the Miller-Rabin algorithm. Notice that the algorithm is correct for all numbers; there is no equivalent of Carmichael numbers with respect to strong pseudoprimes. A number is a strong pseudoprime if and only if it is prime, which is the case if and only if it passes (with probability as close to 1 as desired) the Miller-Rabin primality test. We finish by summarizing the algorithm:

Algorithm 3.4 (Miller-Rabin primality test).

Input: Integers n ⩾ 2 and t ⩾ 1.

Output: If n is prime, output “yes”. If n is not prime, output “no” with probability at least 1 − 1/2^{t}, and “yes” with probability at most 1/2^{t}.

Algorithm: Let n − 1 = 2^{s}l, where l is odd. Pick t independent, uniformly distributed random numbers b_{1}, …, b_{t} ∈ {1, …, n − 1}. For each i, check that one of the following conditions hold: either b_{i}^{l} ≡ 1(mod n) or b_{i}^{2^{r}l} ≡ −1(mod n) for some 0 ⩽ r < s. If this is the case for all b_{i}, output “yes”, else “no”. □