# 9.3 Primality Testing

Suppose we have an integer of 300 digits that we want to test for primality. We know by Exercise 7 in Chapter 3 that one way is to divide by all the primes up to its square root. What happens if we try this? There are around  primes less than . This is significantly more than the number of particles in the universe. Moreover, if the computer can handle  primes per second, the calculation would take around  years. (It’s been suggested that you could go sit on the beach for 20 years, then buy a computer that is 1000 times faster, which would cut the runtime down to  years – a very large savings!) Clearly, better methods are needed. Some of these are discussed in this section.

A very basic idea, one that is behind many factorization methods, is the following.

# Basic Principle

Let  be an integer and suppose there exist integers  and  with , but . Then  is composite. Moreover,  gives a nontrivial factor of .

Proof. Let . If  then , which is assumed not to happen. Suppose . The Proposition in Subsection 3.3.1 says that if  and if , then . In our case, let , let , and let . Then . If , then . This says that , which contradicts the assumption that . Therefore, , so  is a nontrivial factor of .

# Example

Since , but , we know that 35 is composite. Moreover,  is a nontrivial factor of 35.

It might be surprising, but factorization and primality testing are not the same. It is much easier to prove a number is composite than it is to factor it. There are many large integers that are known to be composite but that have not been factored. How can this be done? We give a simple example. We know by Fermat’s theorem that if  is prime, then . Let’s use this to show 35 is not prime. By successive squaring, we find (congruences are mod 35)



Therefore,



Fermat’s theorem says that 35 cannot be prime, so we have proved 35 to be composite without finding a factor.

The same reasoning gives us the following.

# Fermat Primality Test

Let  be an integer. Choose a random integer  with . If , then  is composite. If , then  is probably prime.

Although this and similar tests are usually called “primality tests,” they are actually “compositeness tests,” since they give a completely certain answer only in the case when  is composite. The Fermat test is quite accurate for large . If it declares a number to be composite, then this is guaranteed to be true. If it declares a number to be probably prime, then empirical results show that this is very likely true. Moreover, since modular exponentiation is fast, the Fermat test can be carried out quickly.

Recall that modular exponentiation is accomplished by successive squaring. If we are careful about how we do this successive squaring, the Fermat test can be combined with the Basic Principle to yield the following stronger result.

# Miller-Rabin Primality Test

Let  be an odd integer. Write  with  odd. Choose a random integer  with . Compute . If , then stop and declare that  is probably prime. Otherwise, let . If , then  is composite (and  gives a nontrivial factor of ). If , then stop and declare that  is probably prime. Otherwise, let . If , then  is composite. If , then stop and declare that  is probably prime. Continue in this way until stopping or reaching . If , then  is composite.

# Example

Let . Then , so  and . Let . Then



Since , we conclude that 561 is composite. Moreover, , which is a nontrivial factor of 561.

If  is composite and , then we say that  is a pseudoprime for the base . If  and  are such that  passes the Miller-Rabin test, we say that  is a strong pseudoprime for the base . We showed in Section 3.6 that , so 561 is a pseudoprime for the base 2. However, the preceding calculation shows that 561 is not a strong pseudoprime for the base 2. For a given base, strong pseudoprimes are much more rare than pseudoprimes.

Up to , there are 455052511 primes. There are 14884 pseudoprimes for the base 2, and 3291 strong pseudoprimes for the base 2. Therefore, calculating  will fail to recognize a composite in this range with probability less than 1 out of 30 thousand, and using the Miller-Rabin test with  will fail with probability less than 1 out of 100 thousand.

It can be shown that the probability that the Miller-Rabin test fails to recognize a composite for a randomly chosen  is at most . In fact, it fails much less frequently than this. See [Damgå rd et al.]. If we repeat the test 10 times, say, with randomly chosen values of , then we expect that the probability of certifying a composite number as prime is at most . In practice, using the test for a single  is fairly accurate.

Though strong pseudoprimes are rare, it has been proved (see [Alford et al.]) that, for any finite set  of bases, there are infinitely many integers that are strong pseudoprimes for all . The first strong pseudoprime for all the bases  is 3215031751. There is a 337-digit number that is a strong pseudoprime for all bases that are primes .

Suppose we need to find a prime of around 300 digits. The prime number theorem asserts that the density of primes around  is approximately . When , this gives a density of around . Since we can skip the even numbers, this can be raised to . Pick a random starting point, and throw out the even numbers (and multiples of other small primes). Test each remaining number in succession by the Miller-Rabin test. This will tend to eliminate all the composites. On average, it will take less than 400 uses of the Miller-Rabin test to find a likely candidate for a prime, so this can be done fairly quickly. If we need to be completely certain that the number in question is prime, there are more sophisticated primality tests that can test a number of 300 digits in a few seconds.

Why does the test work? Suppose, for example, that . This means that . Apply the Basic Principle from before. Either , or  and  is composite. In the latter case,  gives a nontrivial factor of . In the former case, the algorithm would have stopped by the previous step. If we reach , we have computed . The square of this is , which must be  if  is prime, by Fermat’s theorem. Therefore, if  is prime, . All other choices mean that  is composite. Moreover, if , then, if we didn’t stop at an earlier step,  with . This means that  is composite (and we can factor ).

In practice, if  is composite, usually we reach  and it is not . In fact, usually . This means that Fermat’s test says  is not prime.

For example, let  and . Since , Fermat’s theorem and also the Miller-Rabin test say that 299 is not prime (without factoring it). The reason this happens is the following. Note that . An easy calculation shows that  and no smaller exponent works. In fact,  if and only if  is a multiple of 12. Since 298 is not a multiple of 12, we have , and therefore also . Similarly,  if and only if  is a multiple of 11, from which we can again deduce that . If Fermat’s theorem (and the Miller-Rabin test) were to give us the wrong answer in this case, we would have needed  to be a multiple of .

Consider the general case , a product of two primes. For simplicity, consider the case where  and suppose  if and only if . This means that  is a primitive root mod ; there are  such  mod . Since , we have



Therefore,  by our choice of , which implies that . Similar reasoning shows that usually  for many other choices of , too.

But suppose we are in a case where . What happens? Let’s look at the example of . Since , we consider what is happening to the sequence  mod 3, mod 11, and mod 17:



Since , we have  mod all three primes. But there is no reason that  is the first time we get  mod a particular prime. We already have  mod 3 and mod 11, but we have to wait for  when working mod 17. Therefore,  mod 3, mod 11, and mod 17, but  is congruent to 1 only mod 3 and mod 11. Therefore,  contains the factors 3 and 11, but not 17. This is why  finds the factor 33 of 561. The reason we could factor 561 by this method is that the sequence  reached 1 mod the primes not all at the same time.

More generally, consider the case  (a product of several primes is similar) and suppose . As pointed out previously, it is very unlikely that this is the case; but if it does happen, look at what is happening mod  and mod . It is likely that the sequences  and  reach  and then 1 at different times, just as in the example of 561. In this case, we will be have  but  for some ; therefore,  but . Therefore, we’ll be able to factor .

The only way that  can pass the Miller-Rabin test is to have  and also to have the sequences  and  reach 1 at the same time. This rarely happens.

Another primality test of a nature similar to the Miller-Rabin test is the following, which uses the Jacobi symbol (see Section 3.10).

# Solovay-Strassen Primality Test

Let  be an odd integer. Choose several random integers  with . If



for some , then  is composite. If



for all of these random , then  is probably prime.

Note that if  is prime, then the test will declare  to be a probable prime. This is because of Part 2 of the second Proposition in Section 3.10.

The Jacobi symbol can be evaluated quickly, as in Section 3.10. The modular exponentiation can also be performed quickly.

For example,



so 15 is not prime. As in the Miller-Rabin tests, we usually do not get  for . Here is a case where it happens:



However, the Solovay-Strassen test says that 341 is composite.

Both the Miller-Rabin and the Solovay-Strassen tests work quickly in practice, but, when  is prime, they do not give rigorous proofs that  is prime. There are tests that actually prove the primality of , but they are somewhat slower and are used only when it is essential that the number be proved to be prime. Most of these methods are probabilistic, in the sense that they work with very high probability in any given case, but success is not guaranteed. In 2002, Agrawal, Kayal, and Saxena [Agrawal et al.] gave what is known as a deterministic polynomial time algorithm for deciding whether or not a number is prime. This means that the computation time is always, rather than probably, bounded by a constant times a power of . This was a great theoretical advance, but their algorithm has not yet been improved to the point that it competes with the probabilistic algorithms.

For more on primality testing and its history, see [Williams].