For some primality tests, the approach of proving a number as composite is to produce an auxiliary number that shows that a property of prime numbers is violated. Such an auxiliary number is called a “witness” for compositeness. When using such a primality test on a composite number, for the test to be correct, at least one “witness” must be found. In this post, we compare the Fermat primality test and the Miller-Rabin test from the standpoint of producing “witnesses”. In this regard, the Fermat test works correctly most of the time. But there is a rare but infinite class of composite numbers for which no Fermat test witness can be found. On the other hand, using the Miller-Rabin test on a composite number, at least one witness can be found (in fact, there are lots of them).
According to Fermat’s little theorem, if is a prime number, then the following congruence holds for all numbers that are coprime to .
If there exists a number such that , then is proved to be composite, in which case the number is said to be a Fermat witness for the compositeness of . If the congruence (1) holds for several values of , then is a likely a prime.
Suppose is a large odd number whose “prime versus composite” status is not known. If the congruence (1) holds for some positive integer , then is said to be a probable prime to base . A probable prime to the base could be prime or could be composite. If the latter, the number is said to be a pseudoprime to base .
This is how the Fermat test (or probable prime test) works. Given that is a large odd number whose “prime versus composite” status is not known, if is not a probable prime to one base , then is proven to be composite and is a Fermat witness for . On the other hand, if is a probable prime to several randomly selected bases, then is a probable prime.
Suppose that you apply the Fermat test on the number and find that is a probable prime to several bases. There are two possibilities. Either is prime or is a pseudoprime to the several bases that are being used. Pseudoprimess to one base are rare. Pseudoprimes to several bases at once are even rarer. For example, according to , there are only 21853 pseudoprimes to the base 2 that are less than . The number of primes below is roughly . So most probable primes to base 2 are primes. Of the 21853 pseudoprimes to the base 2 that are below , 4709 of them are pseudoprimes to the bases 2 and 3, 2522 of them are pseudoprimes to the bases 2, 3 and 5, and 1770 of them are pseudoprimes to the bases 2, 3, 5 and 7. Thus there is indication that the numbers that are pseudoprimes to several bases are very rare. Therefore, the number being a simultaneous pseudoprime to several bases is very strong evidence that is prime. But this is not the end of the story for the Fermat test.
The Fermat test can detect the compositeness of most composite numbers. These are the numbers that are probable prime to one base but are not probable prime to another base. For example, 341 is a probable prime to base 2 since . On the other hand, . Thus 341 is not a probable prime to base 3 (i.e. 3 is a Fermat witness for the compositeness of 341). For integers like 341, they may be probable primes to one base, but they are not probable primes to another base. If there exists at least one Fermat witness for a composite number, there is a good chance that the Fermat test will detect the compositeness.
A odd composite number is said to be a Carmichael number if the congruence (1) holds for all numbers coprime to . The smallest Carmichael number is 561. There is no danger of mistaking a small Carmichael number such as 561 as prime because factoring is possible. Carmichael numbers are rare but there are infinitely of them. So there are large Carmichael numbers (e.g. with hundreds of digits or thousands of digits). The Fermat test fails completely with these large Carmichael numbers. In other words, no matter how many bases are used, it is impossible to find a number that will witness the compositeness of a Carmichael number. Unlike the number 341, the Fermat test will fail to detect the compositeness of a Carmichael number.
Looking for a better type of witness
Let be an odd number with where and is odd. Then compute the following sequence of numbers modulo :
where is some number coprime to . The first term in the sequence can be calculated by using the fast powering algorithm. Each subsequent term is the square of the preceding one. Of course, the last term is the same as , the calculation for (1). Then if this calculation is done on a prime number , the last term in (2) is always a 1. But more can be said about the sequence (2).
The better witnesses and primality test we discuss here are based on this theorem about prime numbers.
If is a prime number, then either one of the following conditions holds:
- for some
for each number that is coprime to .
The theorem just mentioned is the basis of the Miller-Rabin test. If there exists some such that both (2a) and (2b) are not true, then the number is proved to be composite, in which case the number is said to be a witness for the compositeness of . So a witness from the Fermat test standpoint is called Fermat witness. The term witness here refers to the calculation of (2). If the conditions (2a) or (2b) holds for several values of , then is likely a prime number.
Suppose is a large odd number whose “prime versus composite” status is not known. If the conditions (2a) or (2b) holds for some positive integer , then is said to be a strong probable prime to base . A strong probable prime to the base could be prime or could be composite. If the latter, the number is said to be a strong pseudoprime to base .
This is how the Miller-Rabin test (or strong probable prime test) works. Given that is a large odd number whose “prime versus composite” status is not known, if is not a strong probable prime to one base , then is proved to be composite and the number is a witness for . If is a strong probable prime to several randomly chosen bases, then the probability that is composite is smaller than (if bases are used). In other words, the error probability can be made arbitrarily small by using more random bases in the calculation for sequence (2).
The last point about the small error probability is the most important advantage of the Miller-Rabin test over the Fermat test. Let’s look at a small example first. Recall that 561 is the smallest Carmichael number. Note that . The following is the calculation for (2).
The number 561 is a probable prime to base 2 (from a Fermat perspective). Notice that the condition (2a) is not met. The condition (2b) is also not met since the term preceding the first 1 is 67, which is not congruent to -1. So the number 2 is a witness for the compositeness of 561. The Fermat test will have virtually no chance of detecting the compositeness of 561. Yet the strong probable prime test takes only one calculation for 561. In this case at least, it is pretty easy to find a witness.
At least one witness can be found
One characteristic of the strong probable prime test is that there are lots of witnesses when testing composite numbers. In fact, if is a composite number, over 75% of the possible choices of bases are witnesses for . We prove a simpler theorem that if is composite, at least one witness for the compositeness of can be found. Even this much weaker theorem is a big improvement over the Fermat test.
Let be a composite positive odd number. Then there a number that is coprime to such that is not a strong pseudoprime to base .
Proof of Theorem 1
Let such that are odd and are coprime. Consider the following two congruence equations.
By the Chinese remainder theorem (CRT), there is an such that
We can assume that . If not, reduce modulo . Then . If , then for some . This would mean that , contradicting . Similarly . So we have . On the other hand, we have
By CRT, . Let where and odd. Let for some integer . The following calculates and .
The first term in (2) that is a 1 is . The preceding term is not a -1. This shows that the composite number is not a strong pseudoprime to base . Thus for any composite number , there always exists a witness for the compositeness of .
The proof of Theorem 1 is essentially that if is composite, there is a square root other than . This nontrivial square root is a witness to the compositeness of .
The least witness
If is a composite number, there exists a witness for according to Theorem 1. Of all the witnesses for a given composite number , there must be the smallest one. Let be the least witness for the compositeness for the composite number . The number is an interesting one.
In general, the larger is, the harder to find the number . This stems from the fact that strong pseudoprimes are very rare. Most composite numbers are not strong pseudoprimes to base 2. For these composite numbers, . For the strong pseudoprimes to base 2, . For , the composite numbers must be strong pseudoprimes to base 2 and base 3. For , the composite numbers must be strong pseudoprimes to the prime bases 2, 3 and 5. There are only 13 such numbers below . Thus it is not easy to find composite numbers that have large least witnesses.
Two more comments to make. One is that knowing the least integer such that is greater than the first prime numbers can be as a deterministic primality test . This is discussed in the next post. The other is that even though a large means that the composite numbers are rare (under a specific bound). But there are infinitely many of them (over the entire number line). It follows from a theorem in  that for any finite set of integers, there are infinitely many Carmichael numbers whose is not found in the finite set.
- Alford W., Granville A., and Pomerance C., On the difficulty
of finding reliable witnesses, L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory: Proc. ANTS-I, Ithaca, NY, volume 877 of
Lecture Notes in Computer Science, pages 1–16. Springer–Verlag, 1994.
- Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
- Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to , Math. Comp., Volume 35, 1003-1026, 1980.