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.
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 .
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)
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.
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.
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.
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).
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.
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].