Counting Fermat witnesses

For the Fermat primality test, looking for a Fermat witness is the name of the game. Given an integer n for which the “prime or composite” status is not known, if you can find a Fermat witness for n, you can conclude decisively that n is not a prime number. If n is a composite number in reality (but the status is not known to you), how likely is it to find a Fermat witness? In other words, when you use the Fermat primality test on a composite integer, what is the probability of the test giving the correct answer? Or what is the probability of making a mistake? In this post we answer these questions by having a detailed look at Fermat witnesses. This is done through a theorem (see Theorem 1 below) and by counting the numbers of Fermat witnesses of a series of composite integers.

____________________________________________________________________________

Fermat witness

What is a Fermat witness? A Fermat witness is a number that violates the conclusion of Fermat’s little theorem. Here’s the theorem:

    Fermat’s little theorem
    If n is a prime number and if a is an integer that is relatively prime to n, then a^{n-1} \equiv 1 \ (\text{mod} \ n).

If we can find a number a that is relatively prime to n such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we know for sure that n is composite. Such a number a is said to be a Fermat witness for the compositeness of n. For convenience, we say that a potential Fermat witness for the compositeness of n is any integer a in the interval 1<a<n that is relatively prime to n.

To use the Fermat primality test on the integer n, we examine a random sample of potential Fermat witnesses for n. If one of the potential Fermat witnesses in the sample turns out to be a Fermat witness for n, we know with certainty that n is composite. If none of the potential Fermat witnesses in the random sample is a Fermat witness, then n is a likely a prime number.

As with most diagnostic tests, a test can make two types of mistakes – false positives or false negatives. For primality testing, 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 (see Case 1 in the next section). If the Fermat test gives a negative result, it would be a true negative.

On the other hand, the Fermat test can give a false positive. There are two cases for false positives. In one case (Case 2a), the probability of a false positive can be made as low as possible. For the other case (Case 2b), the probability of a false positive is virtually 100%.

____________________________________________________________________________

Looking at different cases

If n is a prime number in reality (but the status is not known before the testing), the Fermat test will always give the correct result. The Fermat test will never make the mistake of declaring a prime number as composite. What if is n is a composite number in reality? How would the test behave? It turns out that if n is a composite number that has a Fermat witness, the test is an effective probabilistic primality test. On the other hand, if n is a composite number that has no Fermat witness, the test will identify n as a prime number (so the test fails completely). Here’s the cases we just describe:

  • Case 1. n is a prime number.
  • Case 2. n is a composite number.
    • Case 2a. n is a composite number that has a Fermat witness.
    • Case 2b. n is a composite number that has no Fermat witness.

Let’s look at the cases in more details. If n is a prime number in reality, then it satisfies Fermat’s little theorem. The congruence a^{n-1} \equiv 1 \ (\text{mod} \ n) is always true. So the Fermat test will always give the correct result when the number being tested is a prime number in reality. In Case 1, it will never identify a prime number as a composite number. As mentioned above, the probability of a false negative is zero.

If n is a composite number that has at least one Fermat witness, there is a chance that the Fermat test can identify n as a prime (i.e. a false positive). However, the probability of making a mistake can be reducdd by increasing the number of potential witnesses to be calculated. Indeed, if we sample k potential witnesses, there is at most a 2^{-k} chance of getting a wrong result. In Case 2a, the probability of error can be made so small that it is practically zero for all practical purposes. In this case, the Fermat test can work truly as a probabilistic primality test. In this case, the probability of a false positive can be made as small as possible.

The last case (Case 2b) is the weakest link in the Fermat test. Any composite number n such that a^{n-1} \equiv 1 \ (\text{mod} \ n) for all a relatively prime to n is said to be a Carmichael number. When the Fermat test is applied on such a number, it will never give the correct conclusion (i.e. it will always give a false positive). It does not matter how many potential Fermat witnesses that are calculated. In fact, calculating a^{n-1} \ (\text{mod} \ n) for a large number of values of a can lead one to believe that this number n is a prime number. In this case, the probability of a false positive is virtually 100%. So the case of Carmichael numbers cannot be totally ignored. There are infinitely many Carmichael numbers (proved in 1994). Fortunately, it is harder and harder to find Carmichael numbers as you move up in the number line. For an illustration that Carmichael numbers are rare, see a discussion in this previous post.

We will see below that for the composite numbers in Case 2a, the Fermat test has a very small probability of a false positive (identifying a composite number as a prime number). On the other hand, for the composite numbers in Case 2b, the Fermat test has a 100% probability of a false positive. Of course, when you test a number for primality, you do not know in advance what case it is. Thus the presence of Carmichael numbers is a concern.

____________________________________________________________________________

A floor for the count of Fermat witnesses

Theorem 1 below sets a floor for Fermat witnesses. Once again, in this theorem we only care about the composite numbers that have at least one Fermat witness. Recall that a potential Fermat witness for the compositeness of n is an integer a in the interval 1<a<n such that a and n are relatively prime, i.e., \text{GCD}(a,n) = 1.

Theorem 1
Let n be a composite integer that has at least one Fermat witness. Then at least half of the potential witnesses for the compositeness of n are Fermat witnesses.

Proof of Theorem 1
Let a be a Fermat witness for n. We claim that if b is a potential Fermat witness that is not a Fermat witness, then a \cdot b is a Fermat witness for n. First of all, a \cdot b is relatively prime to n. Note that the product if two numbers, each of which is relatively prime to n, is once again a number that is relatively prime to n (see Lemma 4 in this previous post). Thus a \cdot b is a potential Fermat witness for n. The following shows that a \cdot b is a Fermat witness for n.

    (a \cdot b)^{n-1}=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 a is a Fermat witness for n and that b is not a Fermat witness for n, which means that b^{n-1} \equiv 1 \ (\text{mod} \ n).

If all the potential Fermat witnesses are Fermat witnesses, then we are done since the conclusion of the theorem is true. Assume that at least one potential Fermat witness is not a Fermat witness. In fact, the following enumerates all potential Fermat witnesses that are not Fermat witnesses:

    b_1,\ b_2,\ \cdots, \ b_k

where k \ge 1 and b_i \not \equiv b_j \ (\text{mod} \ n) for all i \ne j. By the claim established earlier, the following numbers are all Fermat witnesses for n.

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

The above Fermat witnesses are all distinct. If ab_i \equiv ab_j \ (\text{mod} \ n) where i \ne j, then we can multiply both sides by a^{-1} and obtain b_i \equiv b_j \ (\text{mod} \ n), which is not possible. What we have proved is that if there exists one Fermat witness for n and if there are k many distinct potential Fermat witnesses that are not Fermat witnesses, then there are at least k many Fermat witnesses for n. This means that at most half of the potential witnesses are non-Fermat witnesses (if there are more than half, we get a contradiction). Thus at least half of the potential Fermat witnesses are Fermat witnesses. \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. In other words, \phi(n) is the count of the potential Fermat witnesses for n. With this in mind, Theorem 1 can be restated as the following:

Corollary 2
Let n be a composite integer that has at least one Fermat witness. Then the number of Fermat witnesses for the compositeness of n is at least \displaystyle \frac{\phi(n)}{2}.

____________________________________________________________________________

The significance of Theorem 1

Theorem 1 gives a floor on Fermat witnesses for one type of composite numbers, namely the composite numbers that have at least one Fermat witness (put another way, the composite numbers that are not Carmichael numbers). More importantly, Theorem 1 allows us to estimate the probability of error when using the Fermat test on such composite numbers.

When applying the Fermat test on a composite integer n that has at least one Fermat witness, the only scenario in which the Fermat test can make an error (aside from calculation errors of course) is that all the random selections of a are not Fermat witnesses. So you are so unlucky that you happen to pick all values of a that are not Fermat witnesses. What is the probability of that?

Randomly select a potential Fermat witness for n, there is at least 50% chance that it is a Fermat witness and at most 50% chance that it is not a Fermat witness. We have the following statement:

    If n is a composite number that has at least one Fermat witness, and if you sample one potential Fermat witness for n, there is at most a 50% chance that it is not a Fermat witness.

If you pick two values of a at random, there is at most 0.5^2=0.25=25 \% chance that both are not Fermat witnesses. If you pick three values of a at random, there is at most 0.5^3=0.125=12.5 \% chance that you pick non-Fermat witnesses three times in a row. If you pick 10 potential witnesses at random, there is at most

    0.5^{10}=0.000977=0.0977 \%

chance that all ten values of a are not Fermat witnesses. In general, we can make the following statement:

    If n is a composite number that has at least one Fermat witness, then when sampling k many potential Fermat witnesses for n, the probability that none of the k potential witnesses is Fermat witness is 0.5^k.

Recall that the only scenario in which the Fermat test can make a mistake when testing a composite number belonging to Case 2a is that the random sample of values of a contains only non-Fermat witnesses. Thus when the sample size is large, the probability of error can be made very small.

The bottom line is that the more potential witnesses you sample, the less likely that you won’t pick a Fermat witness (i.e., it is more likely that you will pick one). Picking a Fermat witness is essentially a coin toss. If you toss a fair coin many times, it is not likely to get all tails (it is likely to get at least one head).

The calculation for each potential witness a is a^{n-1} \ (\text{mod} \ n). Exponentiation in modular arithmetic can be done using the fast powering algorithm, which is an efficient algorithm that involves repeated squarings and multiplications. Thus if the composite number n happens to be a composite number with a Fermat witness, the Fermat test is very efficient (when used with the fast powering algorithm) and accurate.

Of course, when you test the primality of a number, you do not know which case it belongs to. If you want to avoid the case of Carmichael numbers entirely, you might want to try a primality test that can detect Carmichael numbers (e.g. the Miller-Rabin test).

____________________________________________________________________________

Counting examples

To reinforce the discussion in the previous sections, we count the Fermat witnesses for 10 integers. They are all small numbers (the largest one is a little over 200,000). These integers are composite integers that are not Carmichael numbers. So each has at least one Fermat witness. To count the witnesses, we create a computer program to determine the witness status for all a in 1<a<n that are relatively prime to n. The counts are shown in the following matrix.

    Composite integers that are not Carmichael numbers

    \left[\begin{array}{rrrrrrrrr}      \text{ } & \text{ } & \text{ } & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} \\      n & \text{ } & \phi(n) & \text{ } & \text{Yes} & \text{ } & \text{No} & \text{ } & \text{Yes} \ \% \\      \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }  \\      91 & \text{ } & 72 & \text{ } & 36 & \text{ } & 36  & \text{ } & 50 \% \\      221 & \text{ } & 192 & \text{ } & 176 & \text{ } & 16 & \text{ } & 91.67 \% \\      341 & \text{ } & 300 & \text{ } & 200 & \text{ } & 100 & \text{ } & 66.67 \% \\      5,777 & \text{ } & 5,616 & \text{ } & 5,600 & \text{ } & 16 & \text{ } & 99.72 \% \\      10,873 & \text{ } & 10,660 & \text{ } & 10,656 & \text{ } & 4 & \text{ } & 99.96 \% \\      21,809 & \text{ } & 21,504 & \text{ } & 21,248 & \text{ } & 256 & \text{ } & 98.81 \% \\      50,113 & \text{ } & 42,948 & \text{ } & 42,912 & \text{ } & 36& \text{ } & 99.92 \%  \\      73,861 & \text{ } & 73,312 & \text{ } & 73,296 & \text{ } & 16 & \text{ } & 99.98 \% \\       100,097 & \text{ } & 99,396 & \text{ } & 99,392 & \text{ } & 4 & \text{ } & 100 \% \\      201,217 & \text{ } & 200,260 & \text{ } & 200,256 & \text{ } & 4 & \text{ } & 100 \%    \end{array}\right]

The first column is the 10 integers from 91 to 201,217. The second column is Euler’s phi function, which is the count of all integers a that are relatively prime to n, which is the count of the potential Fermat witnesses for n. For n=91, there are 72 potential Fermat witnesses where exactly half are Fermat witnesses. For the other numbers on the list, the percentages of Fermat witnesses are a lot more than 50%. In fact, for most of them, the Fermat witness percentages are over 99%. For the last two numbers on the list the percentage is virtually 100%.

Consider 201,217, the last number on the list. Applying the Fermat test on the number, it will be hard not to pick up a Fermat witness. With only 4 potential witnesses that are not Fermat witness, it is certain to find one Fermat witness when more than 4 numbers are sampled. In fact, even if just 4 numbers are sampled, there is a virtually 100% chance that a Fermat witness will be found.

Take the number in the above table that has the largest number of non-Fermat witnesses (n=21,809), which has 256 non-Fermat witnesses. It has 21,504 potential witnesses. Out of a random sample of 20 such potential Fermat witnesses, the probability that none of them is a Fermat witness is 3.24 \cdot 10^{-39}, which is practically zero.

The above calculations show that for composite numbers that have at least one Fermat witness, the Fermat test is very accurate with a very high probability. The key is to sample a large enough number of potential witnesses. However for Carmichael numbers, it is totally different story.

As discussed earlier, a Carmichael number is a composite number n that has no Fermat witnesses. Specifically a composite number n is a Carmichael number if a^{n-1} \equiv 1 \ (\text{mod} \ n) for all integers a such that 1<a<n and a and n are relatively prime. The following table is a demonstration of this property.

    The first ten Carmichael numbers

    \left[\begin{array}{rrrrrrrrr}      \text{ } & \text{ } & \text{ } & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} \\      n & \text{ } & \phi(n) & \text{ } & \text{Yes} & \text{ } & \text{No} & \text{ } & \text{Yes} \ \% \\      \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }  \\      561 & \text{ } & 320 & \text{ } & 0 & \text{ } & 320  & \text{ } & 0 \% \\      1,105 & \text{ } & 768 & \text{ } & 0 & \text{ } & 768 & \text{ } & 0 \% \\      1,729 & \text{ } & 1,296 & \text{ } & 0 & \text{ } & 1,296 & \text{ } & 0 \% \\      2,465 & \text{ } & 1,792 & \text{ } & 0 & \text{ } & 1,792 & \text{ } & 0 \% \\      2,821 & \text{ } & 2,160 & \text{ } & 0 & \text{ } & 2,160 & \text{ } & 0 \% \\      6,601 & \text{ } & 5,280 & \text{ } & 0 & \text{ } & 5,280 & \text{ } & 0 \% \\      8,911 & \text{ } & 7,128 & \text{ } & 0 & \text{ } & 7,128& \text{ } & 0 \%  \\      10,585 & \text{ } & 8,064 & \text{ } & 0 & \text{ } & 8,064 & \text{ } & 0 \% \\       15,841 & \text{ } & 12,960 & \text{ } & 0 & \text{ } & 12,960 & \text{ } & 0 \% \\      29,341 & \text{ } & 25,920 & \text{ } & 0 & \text{ } & 25,920 & \text{ } & 0 \%    \end{array}\right]

The above table lists out the first ten Carmichael numbers. Though we can show that each one of them is a Carmichael number by using the Korselt’s Criterion (see here but you have to first factor the numbers). We calculate the Fermat witness status for each potential witness for each n in the table. The above table is a visual demonstration of the fact that the column for the Fermat witnesses is entirely zero! So if you happen to test the primality on such numbers using the Fermat test, you will conclude that they are prime numbers unless you happen to sample a value of a whose GCD with n is greater than one (i.e., the only way you can determine the compositeness of a Carmichael number is to stumble into a GCD witness).

Fermat test does what it does well with the exception of Carmichael numbers. As mentioned earlier, if you want to avoid the trap of working with Carmichael numbers (as rare as they are), you can always switch to a test that will always detect Carmichael numbers (e.g. Miller-Rabin test).

____________________________________________________________________________

\copyright \ 2014 \text{ by Dan Ma}

Advertisements

One thought on “Counting Fermat witnesses

  1. Pingback: A Good Will Hunting Story from China | Math in the Spotlight

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s