The Fermat primality test

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

$n$

$a$

$n$

$a^{n-1} \equiv 1 (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

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 $n$ is not known. If we can find an integer $a$ that is relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ , then we have conclusive proof that $n$ is composite. Such a number $a$ is said to be a Fermat witness for (the compositeness of) $n$ .

The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for $n$ and $a$ , then $n$ is said to be a probable prime to base $a$ . Furthermore, if $n$ happens to be a composite number, then $n$ is said to be a pseudoprime to base $a$ . Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base $a$ .

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 $n$ is found to be a probable prime to all the randomly chosen bases, then $n$ is likely a prime number.

If the number $n$ 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 $n$ is in reality a composite number, the Fermat test can make the mistake of identifying the composite number $n$ 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 $a$ ). 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.

Fermat primality test

$n$

Composite

$n$

Probably Prime

Step 1. Choose a random integer $a \in \left\{2,3,\cdots,n-1 \right\}$ .
Step 2. Compute $\text{GCD}(a,n)$ . If it is greater than 1, then stop and output $n$ is Composite. Otherwise go to the next step.
Step 3. Compute $a^{n-1} \ (\text{mod} \ n)$ .

If $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ , then stop and output $n$ is Composite.
If $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ , then $n$ may be a prime number. Do one of the following:

Return to Step 1 and repeat the process with a new $a$ .
Output $n$ is Probably Prime and stop.

$\text{ }$

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 $a$ such that $1<a<n$ and such that $\text{GCD}(a,n) \ne 1$ , then the integer $n$ is certainly composite. Such a number $a$ is called a GCD witness for the compositeness of $n$ . 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 $n$ 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 $n$ is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that $n$ 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 $n$ is an irrefutable proof that $n$ is composite.

However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number $n$ is said to be a Carmichael number if the above congruence relationship (1) holds for all bases $a$ relatively prime to $n$ . In other words, $n$ is a Carmichael number if $a^{n-1} \equiv 1 (\text{mod} \ n)$ for all $a$ that are relatively prime to $n$ . Saying it in another way, $n$ is a Carmichael number if there exists no Fermat witness for $n$ .

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.

Theorem 1

$n$

$a$

$1<a<n$

$n$

$a$

$1<a<n$

$n$

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 $n$ 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 $n$ . So if $k$ values of $a$ are randomly selected, there is at most $0.5^k$ probability that the Fermat test will not detect the compositeness of the composite number $n$ (i.e. making a mistake). So the probability of a false positive is at most $0.5^k$ . For a large enough $k$ , this probability is practically zero.

Proof of Theorem 1
A base to which $n$ is a pseudoprime or not a pseudoprime should be a number in the interval $1<a<n$ that is relatively prime to $n$ . If $n$ is a pseudoprime to base $a$ , then $a$ raised to some power is congruent to 1 modulo $n$ . For this to happen, $a$ must be relatively prime to the modulus $n$ . For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer $n$ (see the post on Euler’s phi function).

Let $a$ be a base to which $n$ is not a pseudoprime. We make the following claim.

Claim

$b$

$1<b<n$

$n$

$b$

$n$

$a \cdot b$

Since both integers $a$ and $b$ are assumed to be relatively prime to $n$ , the product $a \cdot b$ is also relatively prime to $n$ (see Lemma 4 in this post). Now consider the congruence $(ab)^{n-1} \ (\text{mod} \ n)$ , which is derived as follows:

$(ab)^{n-1} \equiv a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$

In the above derivation, we use the fact that $n$ is not a pseudoprime to base $a$ and $n$ is a pseudoprime to base $b$ . The above derivation shows that $n$ is not a pseudoprime to base $ab$ .

If $n$ is not a pseudoprime to all bases in $1<w<n$ , then we are done. So assume that $n$ is a pseudoprime to at least one base. Let $b_1,b_2,\cdots,b_k$ enumerate all bases to which $n$ is a pseudoprime. We assume that the $b_j$ are all distinct. So $b_i \not \equiv b_j \ (\text{mod} \ n)$ for all $i \ne j$ . By the above claim, the composite number $n$ is not a pseudoprime to all the following $k$ numbers:

$a \cdot b_1, \ a \cdot b_2, \cdots, \ a \cdot b_k$

It is also clear that $a \cdot b_i \not \equiv a \cdot b_j \ (\text{mod} \ n)$ for $i \ne j$ . What we have just shown is that there are at least as many bases to which $n$ is not a pseudoprime as there are bases to which $n$ is a pseudoprime. This means that $n$ is not a pseudoprime to at least 50% of the bases that are relatively prime to $n$ . In other words, as long as there exists one Fermat witness for $n$ , at least 50% of the bases are Fermat witnesses for $n$ . It then follows that $n$ is a pseudoprime to no more than 50% of the bases relatively prime to $n$ . $\blacksquare$

There is another way to state Theorem 1. Recall that Euler’s phi function $\phi(n)$ is defined to be the number of integers $a$ in the interval $1<a<n$ that are relatively prime to $n$ . With this in mind, Theorem 1 can be restated as the following:

Corollary 2

$n$

$\displaystyle \frac{\phi(n)}{2}$

$1<a<n$

___________________________________________________________________

Concluding remarks

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.

___________________________________________________________________
$\copyright \ \ 2014 - 2015 \ \text{Dan Ma}$ (Revised march 29, 2015)

4 thoughts on “The Fermat primality test”

Pingback: Using Fermat’s Little Theorem to Test Primality | Exploring Number Theory
Pingback: Fermat’s Little Theorem as a primality testing | All Math Considered
Nick on August 12, 2017 at 11:19 am said:

I dont see why Carmichaels are a problem. 561 is divisible by 3. The gcd(561,3)=3, so in performing the fermat test on 561 on just the first few integer bases will prove compositeness immediately.

LikeLike

Reply ↓
This is a fake email on September 18, 2018 at 5:32 pm said:

Carmichael numbers don’t pass the tests for all values of a, they just past for a large percentage of them. For example 561 fails on 264. the reason that Carmichael numbers are bad is they pass a large number of these tests, with some of them failing on less then 2% of the possible values for a.

LikeLike

Reply ↓

Mathematical Cryptography

focusing on the math in public key cryptography

The Fermat primality test

4 thoughts on “The Fermat primality test”

Leave a comment Cancel reply

Share this:

Related

4 thoughts on “The Fermat primality test”

Leave a comment Cancel reply