Fermat’s little theorem describes a property that is common to all prime numbers. This property can be used as a way to detect the “prime or composite” status of an integer. Primality testing using Fermat’s little theorem is called the Fermat primality test. In this post, we explain how to use this test and to discuss some issues surrounding the Fermat test.
Describing the test
The Fermat primality test, as mentioned above, is based on Fermat’s little theorem. The following is the statement of the theorem.
Fermat’s little theorem
If is a prime number and if is an integer that is relatively prime to , then the following congruence relationship holds:
The above theorem indicates that all prime numbers possess a certain property. Therefore if a given positive integer does not possess this property, we know for certain that this integer is not prime. Suppose that the primality of an integer is not known. If we can find an integer that is relatively prime to such that , then we have conclusive proof that is composite. Such a number is said to be a Fermat witness for (the compositeness of) .
The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for and , then is said to be a probable prime to base . Furthermore, if happens to be a composite number, then is said to be a pseudoprime to base . Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base .
The Fermat primality test from a compositeness perspective is about looking for Fermat witnesses. If a Fermat witness is found, the number being tested is proved to be composite. On the other hand, the Fermat primality test, from a primality perspective, consists of checking the congruence relation (1) for several bases that are randomly selected. If the number is found to be a probable prime to all the randomly chosen bases, then is likely a prime number.
If the number is in reality a prime number, then the Fermat test will always give the correct result (as a result of Fermat’s little theorem). If the number is in reality a composite number, the Fermat test can make the mistake of identifying the composite number as prime (i.e. identifying a pseudoprime as a prime). For most composite numbers this error probability can be made arbitrarily small (by testing a large number of bases ). But there are rare composite numbers that evade the Fermat test. Such composite numbers are called Carmichael numbers. No matter how many bases you test on a Carmichael number, the Fermat test will always output Probably Prime. Carmichael numbers may be rare but there are infinitely many of them over the entire number line. More about Carmichael numbers below.
The following describes the steps of the Fermat primality test.
The exponentiation in Step 3 can be done by the fast powering algorithm. This involves a series of squarings and multiplications. Even for numbers that have hundreds of digits, the fast powering algorithm is efficient.
One comment about Step 2 in the algorithm. Step 2 could be called the GCD test for primality. If you can find an integer such that and such that , then the integer is certainly composite. Such a number is called a GCD witness for the compositeness of . So the Fermat test as described above combines the GCD test and the Fermat test. We can use the Euclidean algorithm to find the GCD. If we happen to stumble upon a GCD witness, then we can try another for a candidate of a prime number. For most composite numbers, it is not likely to stumble upon a GCD witness. Thus when using the Fermat test, it is likely that Step 3 in the algorithm is used.
An example of Fermat primality testing is the post called A primality testing exercise from RSA-100.
More about the test
When using the Fermat test, what is the probability of the test giving the correct result? Or what is the probability of making an error? Because the Fermat test is not a true probabilistic primality test, the answers to these questions are conditional. In one scenario which covers most of the cases, the test works like an efficient probabilistic test. In another scenario which occurs very rarely, the Fermat test fails miserably.
As with most diagnostic tests, the Fermat test can make two types of mistakes – false positives or false negatives. For primality testing discussed in this post, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number.
For the Fermat test, there is no false negative. If is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that be declared a composite number. Thus if the Fermat test gives a negative result, it would be a true negative. In other words, finding a Fermat witness for is an irrefutable proof that is composite.
However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number is said to be a Carmichael number if the above congruence relationship (1) holds for all bases relatively prime to . In other words, is a Carmichael number if for all that are relatively prime to . Saying it in another way, is a Carmichael number if there exists no Fermat witness for .
The smallest Carmichael number is 561. Carmichael numbers are rare but there are infinitely many of them. The existence of such numbers poses a challenge for the Fermat test. If you apply the Fermat test on a Carmichael number, the outcome will always be Probably Prime. So the Fermat test will always give a false positive when it is applied on a Carmichael number. To put it in another way, with respect to Carmichael numbers, the error probability of the Fermat test is virtually 100%!
So should a primality tester do? To keep things in perspective, Carmichael numbers are rare (see this post). If the primality testing is done on randomly chosen numbers, choosing a Carmichael number is not likely. So the Fermat test will often give the correct results. For those who are bothered by the nagging fear of working with Carmichael numbers, they can always switch to a Carmichael neutral test such as the Miller-Rabin test.
One bright spot about the Fermat test
There is one bright spot about the Fermat test. When applying the Fermat test on numbers that are not Carmichael numbers, the error probability can be made arbitrarily small. In this sense the Fermat test works like a true probabilistic primality test. Consider the following theorem.
Let be a composite integer such that it is not a pseudoprime to at least one base (i.e. has a Fermat witness). In other words, is not a Carmichael number. Then is not a pseudoprime to at least half of the bases () that are relatively prime to . In other words, is a pseudoprime to at most half of the bases () that are relatively prime to .
Theorem 1 means that the Fermat test can be very accurate on composite numbers that are not Carmichael numbers. As long as there is one base to which the composite number is not a pseudoprime (i.e. as long as there is a Fermat witness for the composite number in question), there will be enough of such bases (at least 50% of the possible bases). As a result, it is likely that the Fermat test will find a witness, especially if the tester is willing to use enough bases to test and if the bases are randomly chosen. When a base is randomly chosen, there is at least a 50% chance that the number is not a pseudoprime to that base (i.e. the Fermat test will detect the compositeness) or putting it in another way, there is at most a 50% chance that the Fermat test will not detect the compositeness of the composite number . So if values of are randomly selected, there is at most probability that the Fermat test will not detect the compositeness of the composite number (i.e. making a mistake). So the probability of a false positive is at most . For a large enough , this probability is practically zero.
Proof of Theorem 1
A base to which is a pseudoprime or not a pseudoprime should be a number in the interval that is relatively prime to . If is a pseudoprime to base , then raised to some power is congruent to 1 modulo . For this to happen, must be relatively prime to the modulus . For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer (see the post on Euler’s phi function).
Let be a base to which is not a pseudoprime. We make the following claim.
If is a number such that and such that is a pseudoprime to base , then is not a pseudoprime to base .
Since both integers and are assumed to be relatively prime to , the product is also relatively prime to (see Lemma 4 in this post). Now consider the congruence , which is derived as follows:
In the above derivation, we use the fact that is not a pseudoprime to base and is a pseudoprime to base . The above derivation shows that is not a pseudoprime to base .
If is not a pseudoprime to all bases in , then we are done. So assume that is a pseudoprime to at least one base. Let enumerate all bases to which is a pseudoprime. We assume that the are all distinct. So for all . By the above claim, the composite number is not a pseudoprime to all the following numbers:
It is also clear that for . What we have just shown is that there are at least as many bases to which is not a pseudoprime as there are bases to which is a pseudoprime. This means that is not a pseudoprime to at least 50% of the bases that are relatively prime to . In other words, as long as there exists one Fermat witness for , at least 50% of the bases are Fermat witnesses for . It then follows that is a pseudoprime to no more than 50% of the bases relatively prime to .
There is another way to state Theorem 1. Recall that Euler’s phi function is defined to be the number of integers in the interval that are relatively prime to . With this in mind, Theorem 1 can be restated as the following:
Let be a composite integer such that it is not a pseudoprime to at least one base. Then is not a pseudoprime to at least many bases in the interval .
Of course, Theorem 1 works only for the composite numbers that are not pseudoprime to at least one base (i.e. they are not Carmichael numbers). When you test the compositeness of a number, you do not know in advance if it is Carmichael or not. On the other hand, if the testing is done on randomly chosen numbers, it is not likely to randomly stumble upon Carmichael numbers. The Fermat test works well for the most part and often give the correct results. If one is concerned about the rare chance of a false positive in the form of a Carmichael number, then the Miller-Rabin test will be a good alternative.
The original post was written in August 10, 2013. On March 29, 2015, this post is replaced with a blog post called The Fermat primality test from the companion math crypto blog.