Primality testing

Section 6.3 Primality testing

One of the most important areas where non-deterministic methods are used in cryptography is in the area of producing and testing numbers that are highly likely to be prime - that is, it is quite expensive to determine with absolute certainty that a number \(n\) is prime, but it can be checked to any amount of desired likelihood. (Such primes are sometimes referred to as industrial-grade primes - that is, good enough for application.) The idea is that even if the tests miss an occasional number that isn't prime, it happens so infrequently that the economic cost of looking for one is prohibitive.

Recall that a composite number is a number that has two or more non-trivial factors. We'll begin by looking at conditions that prime numbers always satisfy. What springs to mind is Fermat's little theorem Theorem 2.6.1. We will adopt a slightly modified version that removes the restrictions on \(a\text{.}\)

Theorem 6.3.1. Modified Fermat's theorem.

\(p\)\(a\)

\begin{equation*} a^p \equiv a \bmod p. \end{equation*}

Fermat's little theorem gives us a test for compositeness: if \(a^p \neq a \bmod p\text{,}\) then \(p\) cannot be prime. For example, suppose that we want to know if \(n = 9\) is prime (presuming that we don't know how to factor it). On checking the Fermat condition for say \(a = 2\text{,}\) we see that

\begin{equation*} 2^9 \equiv 8 \bmod 9 \end{equation*}

and so \(9\) (shockingly) cannot be prime. This sort of test is exclusive -- we can exclude numbers that fail, but passing the test for a given value of \(a\) does not mean that \(n\) is prime! For example,

\begin{equation*} 6^{21} \equiv 6 \bmod 21 \end{equation*}

and yet 21 is obviously not prime.

We take the position that 2 “sees” the compositeness of 9, but that 6 does not see the compositeness of 21. In this light, we define the notion of a witness of compositeness.

Definition 6.3.2.

A number \(a\) is said to be a (Fermat) witness for the compositeness of a composite number \(n\) if

\begin{equation*} a^n \neq a \bmod n. \end{equation*}

We're left with the following idea: If we suspect that a number \(n\) is prime, check lots of numbers \(a\) as potential witnesses of the compositeness of \(n\text{.}\) If we don't find any witnesses, perhaps we could conclude that \(n\) is prime. The issue with this approach is the existence of a set of numbers called Carmichael numbers, which have the property of possessing no Fermat witnesses. As an example, \(n = 531 = 3 \cdot 11 \cdot 17\) has the property that

\begin{equation*} a^{531} = a \bmod 531 \end{equation*}

for every integer \(a\text{,}\) and thus has no witnesses to the fact that it is composite. There are infintely many Carmichael numbers, and so it behooves us to develop a test so that every composite \(n\) has lots of witnesses.

One such test is called the Miller-Rabin test, which relies on Fermat's little theorem as its background assumption but provides a further discrimination that gives every composite number lots of witnesses.

Theorem 6.3.3.

\(p\)

\begin{equation*} p - 1 = 2^k q \text{ where } q \text{ is odd.} \end{equation*}

\(a\)\(p \nmid a\text{.}\)

\(\displaystyle a^q \equiv 1 \bmod p;\)
A number in the list
\begin{equation} a^q, a^{2q}, a^{4q} \ldots, a^{2^{k-1}q}\label{eq-mr-list}\tag{6.3.1} \end{equation}
is congruent to \(-1 \bmod p\text{.}\)

Proof.

The basic idea of the proof is that \(\sqrt{1} = \pm 1\text{.}\) By Fermat's theorem, we know that

\begin{equation*} a^{2^k q} = a^{p-1} \equiv 1 \mod p. \end{equation*}

The list

\begin{equation*} a^q, a^{2q}, \ldots, a^{2^{k-1}q}, a^{2^k q} = 1 \end{equation*}

is a list of repeated squarings. Since the last number is 1, the previous number must have been 1 or -1. If the previous number is -1, we're finished. If the previous number is 1, then the number prior to that much have been 1 or -1 and so on down the chain. If we reach the first number in the list, it must be 1 or -1 because the next number was 1. If it is -1, then we're done. If it is 1, we're in the first condition, completing the proof.

The theorem gives the underlying condition for the Miller-Rabin test for compositeness.

Definition 6.3.4.

Let \(n\) be odd and write \(n-1 = 2^k q\) with \(q\) odd. An integer \(a\) with \(\gcd(a,n) = 1\) is a Miller-Rabin witness for the compositeness of \(n\) if

\(a^q \neq 1 \bmod n \) and
\(a^{2^i q} \neq -1 \bmod n\) for any \(i = 1, \ldots, k-1\)

By Theorem 6.3.3, if \(n\) has a Miller-Rabin witness then it must be composite. Thus, we can formulate the Miller-Rabin test:

Algorithm 6.3.5.

\(n\)\(a\)

If \(n\) is even, then \(n\) is composite.
If \(1 \lt \gcd(a, n) \lt n\text{,}\) then \(n\) is composite.
Write \(n - 1 = 2^k q\)
Set \(a = a^q \bmod n\) and \(i=0\text{.}\)
If \(a = 1 \bmod n\text{,}\) the test is inconclusive.
If \(a = -1 \bmod n\text{,}\) the test is inconclusive.
If \(i \lt k-1\text{,}\) set \(a = a^2 \mod n\text{,}\) increment \(i\text{,}\) and return to 6.
Else \(n\) is composite.

Python note: the method for the step where all of the factors of 2 are pulled out of \(n-1\) might seem somewhat unclear. A useful command in this case is divmod, which is the library function for division with remainder. A segment of hint code follows.

Composite numbers have lots of Miller-Rabin witnesses.

Proposition 6.3.6.

Let \(n\) be an odd composite number. Then at least 75% of integers \(1 \lt a \leq n-1\) are Miller-Rabin witnesses for the compositeness of \(n\text{.}\)

In some sense, we have the basis for a nondeterministic test for the primeness of an integer now. We know that if \(n\) is composite, we have at least a 75% chance of finding a witness for any given \(a\) that we test. That is, we have a 25% chance at most to fail. If we try lots of values, and they all fail to be witnesses for \(n\text{,}\) then it becomes increasingly likely that \(n\) is prime.

The situation is slighly complicated by the fact that the probabilities are what as known as conditional: that is, when \(n\) is composite, 25% of numbers fail to be witnesses, but when \(n\) is prime, 100% of numbers fail to be witnesses. Nevertheless, the basic intuition should be something like “If \(n\) is composite, then the probability that 10 numbers fail to be Miller-Rabin witnesses for \(n\) is \(.25^{10} \approx 10^{-6}\)”. That is, getting 10 or 100 or 1000 failed witnesses makes it exceedingly unlikely that \(n\) is composite. The exact calculation of the probability will have to wait until we have looked more closely at conditional probability.

One might reasonably ask if there are efficient ways of generating candidate primes. In fact, there are many formulas that are much more likely to produce a prime than a random number generator. Further, we can exclude many possible values for \(n\) with divisibilty rules and quick divisions (say by every number up to 10000) before we apply a computationally expensive MR-test.

Finally, I'll point out that there are deterministic methods for checking that a number is prime that run in polynomial time but these algorithms require that we assume the truth of perhaps the most famous and important unsolved problems in mathematics, the Riemann hypothesis, which concerns the distribution of prime numbers in the real line. More than 150 years of work has gone into proving or disproving the hypothesis, which to the present has resisted giving up its secrets.

Mathematical Cryptography