1.3 Primality testing

1.3 Primality testing

Is there some litmus test that will tell us whether a number is prime without actually trying to factor the number? We place our hopes in a theorem from the year 1640.

Fermat’s little theorem $Hp$ is prime, then for every $1\le a<p,$

a ^ p - 1 ≡ 1 ±od p.$$a^{p-1}\equiv 1(\mathrm{mod}p).$$

Proof

Let S be the nonzero integers modulo $p;$ that is, $S=\{1,2,\dots ,p-1\}$ . Here’s the crucial observation: the effect of multiplying these numbers by a (modulo $p)$ is simply to permute them. For instance, here’s a picture of the case $a=3,p=7;$

Let’s carry this example a bit further. From the picture, we can conclude

{1, 2, … , 6 } = {3 · 1 bmod 7, 3 · 2 bmod 7, … , 3 · 6 bmod 7 }.$$\{1,2,\dots ,6\}=\{3\cdot 1\mathrm{mod}7,3\cdot 2\mathrm{mod}7,\dots ,3\cdot 6\mathrm{mod}7\}.$$

Multiplying all the numbers in each representation then gives $6!\equiv 3^6\cdot 6!$ (mod 7), and dividing by 6! we get $3^6\equiv 1$ (mod $7)$ , exactly the result we wanted in the case $a=3,p=7$

Now let’s generalize this argument to other values of a and $p,$ with $S=\{1,2,\dots ,p-1\}$ We’ll prove that when the elements of S are multiplied by $a$ modulo $p,$ the resulting numbers are all distinct and nonzero. And since they lie in the range $[1,p-1]$ , they must simply be a permutation of S.

The numbers $a\cdot i$ mod $p$ are distinct because if $a\cdot i\equiv a\cdot j$ (mod $p)$ , then dividing both sides by a gives $i\equiv j$ (mod $p)$ . They are nonzero because $a\cdot i\equiv 0$ similarly implies $i\equiv 0$ . (And we can divide by $a,$ because by assumption it is nonzero and therefore relatively prime to $p.)$

We now have two ways to write set S:

S = {1, 2, … , p - 1 } = {a · 1 bmod p, a · 2 bmod p, … , a · (p - 1) bmod p }.$$S=\{1,2,\dots ,p-1\}=\{a\cdot 1\mathrm{mod}p,a\cdot 2\mathrm{mod}p,\dots ,a\cdot (p-1)\mathrm{mod}p\}.$$

We can multiply together its elements in each of these representations to get

(p - 1)! ≡ a ^ p - 1 · (p - 1)! ±od p.$$(p-1)!\equiv a^{p-1}\cdot (p-1)!(\mathrm{mod}p).$$

Dividing by $(p-1)!$ (which we can do because it is relatively prime to $p,$ since $p$ is assumed prime) then gives the theorem.

This theorem suggests a “factorless” test for determining whether a number N is prime:

Figure 1.7An algorithm for testing primality.

function primality($N$) Input: Positive integer N Output: yes/no

Pick a positive integer $a<N$ at random if $a^{N-1}\equiv 1(\mathrm{mod}N)$: return yes else: return no

text Pick some a longrightarrow boxed text Is a ^ N - 1 ≡ 1 bmod N? l text Pass text Fail l text “prime” text “composite”$$\text{ Pick some }a⟶\boxed{\text{ Is }{a}^{N-1}\equiv 1\mathrm{mod}N?}\begin{array}{l}\text{ Pass }\\ \text{ Fail }\end{array}\begin{array}{l}\text{ “prime” }\\ \text{ “composite” }\end{array}$$

The problem is that Fermat’s theorem is not an if-and-only-if condition; it doesn’t say what happens when N is not prime, so in these cases the preceding diagram is questionable. In fact, it is possible for a composite number N to pass Fermat’s test (that is, $a^{N-1}\equiv 1$ mod N) for certain choices of $a.$ For instance, $341=11\cdot 31$ is not prime, and yet $2^{340}\equiv 1$ mod 341. Nonetheless, we might hope that for composite N, most values of $a$ will fail the test. This is indeed true, in a sense we will shortly make precise, and motivates the algorithm of Figure 1.7: rather than fixing an arbitrary value of a in advance, we should choose it randomly from $\{1,\dots ,N-1\}$

In analyzing the behavior of this algorithm, we first need to get a minor bad case out of the way. It turns out that certain extremely rare composite numbers $N_{;}$ , called Carmichael numbers, pass Fermat’s test for all a relatively prime to N. On such numbers our algorithm will fail; but they are pathologically rare, and we will later see how to deal with them (page 36), so let’s ignore these numbers for the time being.

In a Carmichael-free universe, our algorithm works well. Any prime number N will of course pass Fermat’s test and produce the right answer. On the other hand, any non-Carmichael composite number N must fail Fermat’s test for some value of $a;$ and as we will now show, this implies immediately that N fails Fermat’s test for at least half the possible values of a!

Lemma

$\mathcal{I}f{a}^{N-1}\not\equiv 1$ mod N for some a relatively prime to $N,$ then it must hold for at least half the choices $ofa<N$

Proof

Fix some value of a for which $a^{N-1}\not\equiv 1$ mod N. The key is to notice that every element $b<N$ that passes Fermat’s test with respect to N (that is, $b^{\bar{N}-1}\equiv 1$ mod N) has a twin, $a\cdot b,$ that fails the test:

(a · b) ^ N - 1 ≡ a ^ N - 1 · b ^ N - 1 ≡ a ^ N - 1 not ≡ 1 bmod N.$$(a\cdot b{)}^{N-1}\equiv a^{N-1}\cdot b^{N-1}\equiv a^{N-1}\not\equiv 1\mathrm{mod}N.$$

Moreover, all these elements $a\cdot b,$ for fixed a but different choices of $b,$ are distinct, for the same reason $a\cdot i\not\equiv a\cdot j$ in the proof of Fermat’s test: just divide by $a.$

The set {^{1, 2, . . . , N} − ¹}

b	a·b
Pass	Fail

The one-to-one function $b\mapsto a\cdot b$ shows that at least as many elements fail the test as pass it. ı

Hey, that was group theory!

For any integer N, the set of all numbers mod N that are relatively prime to N constitute what mathematicians call a group:

There is a multiplication operation defined on this set.

The set contains a neutral element (namely 1: any number multiplied by this remains unchanged).

All elements have a well-defined inverse.

This particular group is called the multiplicative group of N, usually denoted ${\mathbb{Z}}_N^{\ast }$ .

Group theory is a very well developed branch of mathematics. One of its key concepts is that a group can contain a su ${\partial }_{bgroup-a}$ subset that is a group in and of itself. And an important fact about a subgroup is that its size must divide the size of the whole group.

Consider now the set $B=\{b:b^{N-1}\equiv 1$ mod N . It is not hard to see that it is a subgroup of ${\mathbb{Z}}_N^{\ast }$ (just check that B is closed under multiplication and inverses). Thus the size of B must divide that of ${\mathbb{Z}}_N^{\ast }$ Which means that if B doesn’t contain all of ${\mathbb{Z}}_N^{\ast }$ , the next largest size it can have is $|{\mathbb{Z}}_N^{\ast }|/2$

We are ignoring Carmichael numbers, so we can now assert

If N is prime, then $a^{N-1}\equiv 1$ mod N for all $a<N.$

If N is not prime, then $a^{N-1}\equiv 1$ mod N for at most half the values of $a<N$

The algorithm of Figure 1.7 therefore has the following probabilistic behavior.

Pr(Algorithm1.7 returns yes when N is prime) = 1

Pr(Algorithm1.7 returns yes when N is not prime) $\le \frac{1}{2}$

We can reduce this one-sided error by repeating the procedure many times, by randomly picking several values of a and testing them all (Figure 1.8).

Pr(Algorithm1.8 returns yes when N is not prime) $\le \frac{1}{2^k}$

Figure 1.8An algorithm for testing primality, with low error probability.

function primality2($N$) Input: Positive integer N Output: yes/no

Pick positive integers $a_1,a_2,\dots ,a_k<N$ at random if $a_i^{N-1}\equiv 1(\mathrm{mod}N)$ for all $i=1,2,\dots ,k$: return yes else: return no

This probability of error drops exponentially fast, and can be driven arbitrarily low by choosing k large enough. Testing $k=100$ values of a makes the probability of failure at most $2^{-100}$ which is miniscule: far less, for instance, than the probability that a random cosmic ray will sabotage the computer during the computation!

Box: Carmichael numbers

The smallest Carmichael number is 561. It is not a prime: 561 = 3 11 17; yet it fools the Fermat test, because $a^{560}\equiv 1$ (mod 561) for all values of a relatively prime to 561. For a long time it was thought that there might be only finitely many numbers of this type; now we know they are infinite, but exceedingly rare.

There is a way around Carmichael numbers, using a slightly more refined primality test due to Rabin and Miller. Write $N-1$ in the form $2^{t}u$ As before we’ll choose a random base a and check the value of $a^{N-1}$ mod N. Perform this computation by first determining $a^u$ mod N and then repeatedly squaring, to get the sequence:

a ^ u bmod N, a ^ 2 u bmod N, … , a ^ 2 ^ t u = a ^ N - 1 bmod N.$$a^u\mathrm{mod}N,a^{2u}\mathrm{mod}N,\dots ,a^{2^{t}u}=a^{N-1}\mathrm{mod}N.$$

$\mathrm{If}{a}^{N-1}\ne 1$ mod N, then N is composite by Fermat’s little theorem, and we’re done. But if $a^{N-1}\equiv 1$ mod N, we conduct a little follow-up test: somewhere in the preceding sequence, we ran into a 1 for the first time. If this happened after the first position (that is, $\mathrm{if}{a}^u$ mod $N\ne$ 1), and if the preceding value in the list is not 1 mod N, then we declare N composite.

In the latter case, we have found a nontrivial square root of 1 modulo N: a number that is not 1 mod N but that when squared is equal to 1 mod N. Such a number can only exist if N is composite (Exercise1.40). It turns out that if we combine this square-root check with our earlier Fermat test, then at least three-fourths of the possible values of a between 1 and $N-1$ will reveal a composite N, even if it is a Carmichael number.

1.3.1 Generating random primes

We are now close to having all the tools we need for cryptographic applications. The final piece of the puzzle is a fast algorithm for choosing random primes that are a few hundred bits long. What makes this task quite easy is that primes are abundant—a random n-bit number has roughly a one-in-n chance of being prime (actually about $1/(\ln 2^n)\approx 1.44/n)$ . For instance, about 1 in 20 social security numbers is prime!

Lagrange’s prime number theorem Let $\pi (x)$ be the number of primes $\le x$ . Then $\pi (x)$ ≈ $x/(\ln x)$ or more precⁱse^l$y$

lim _ x → ∞ frac π (x)(x / ln x) = 1.$$\underset{x\to \infty }{\lim }\frac{\pi (x)}{(x/\ln x)}=1.$$

Such abundance makes it simple to generate a random n-bit prime:

Pick a random n-bit number N.

Run a primality test on N.

If it passes the test, output N; else repeat the process.

How fast is this algorithm? If the randomly chosen N is truly prime, which happens with probability at least $1/n$ , then it will certainly pass the test. So on each iteration, this procedure has at least a $1/n$ chance of halting. Therefore on average it will halt within $O(n)$ rounds (Exercise1.34).

Next, exactly which primality test should be used? In this application, since the numbers we are testing for primality are chosen at random rather than by an adversary, it is sufficient to perform the Fermat test with base $a=2$ (or to be really safe, $a=2,3,5)$ , because for random numbers the Fermat test has a much smaller failure probability than the worst-case $1/2$ bound that we proved earlier. Numbers that pass this test have been jokingly referred to as “industrial grade primes.” The resulting algorithm is quite fast, generating primes that are hundreds of bits long in a fraction of a second on a PC.

The important question that remains is: what is the probability that the output of the algorithm is really prime? To answer this we must first understand how discerning the Fermat test is. As a concrete example, suppose we perform the test with base $a=2$ for all numbers $N\le 25\times 10^9$ . In this range, there are about $10^9$ primes, and about 20,000 composites that pass the test (see the following figure). Thus the chance of erroneously outputting a composite is approximately $20,000/10^9=2\times 10^{-5}$ . This chance of error decreases rapidly as the length of the numbers involved is increased (to the few hundred digits we expect in our applications).

Box: Randomized algorithms: a virtual chapter

Surprisingly—almost paradoxically—some ofthe fastest and most clever algorithms we have rely on chance: at specified steps they proceed according to the outcomes of random coin tosses. These randomized algorithms are often very simple and elegant, and their output is correct with high probability. This success probability does not depend on the randomness of the input; it only depends on the random choices made by the algorithm itself.

Instead of devoting a special chapter to this topic, in this book we intersperse randomized algorithms at the chapters and sections where they arise most naturally. Furthermore, no specialized knowledge of probability is necessary to follow what is happening. You just need to be familiar with the concept of probability, expected value, the expected number of times we must flip a coin before getting heads, and the property known as “linearity of expectation.”

Here are pointers to the major randomized algorithms in this book: One of the earliest and most dramatic examples of a randomized algorithm is the randomized primality test of Figure 1.8. Hashing is a general randomized data structure that supports inserts, deletes, and lookups and is described later in this chapter, in Section 1.5. Randomized algorithms for sorting and median finding are described in Chapter 2. A randomized algorithm for the min cut problem is described in the box on page 143. Randomization plays an important role in heuristics as well; these are described in Section 9.3. And finally the quantum algorithm for factoring (Section 10.7) works very much like a randomized algorithm, its output being correct with high probability—except that it draws its randomness not from coin tosses, but from the superposition principle in quantum mechanics.

Virtual exercises: 1.29, 1.34, 2.24, 9.8, 10.8.