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}

Factorization versus primality testing

Let n be a large positive integer whose “prime versus composite” status is not known. One way to know whether n is prime or composite is to factor n into its prime factors. If there is a non-trivial factor (one that is neither 1 nor n), it is composite. Otherwise n is prime. This may sound like a reasonable approach in performing primality testing – checking whether a number is prime or composite. In reality, factoring and primality testing, though related, are very different problems. For a very large number (e.g. with at least 300 decimal digits), it is possible that, even with the state of the art in computing, factoring it may take more than a few million years. On the other hand, it will take a modern computer less than a second to determine whether a 300-digit number is prime or composite. Interestingly this disparity is one reason that makes the RSA work as a practical and secure cryptosystem. In this post, we use the RSA cryptosystem as an example to give a sense that factoring is a “hard” problem while primality testing is an “easy” problem. The primality test used in the examples is the Fermat primality test.

____________________________________________________________________________

The brute force approach

There is a natural and simple approach in factoring, which is to do trial divisions. To factor the number n, we divide n by every integer a in the range 1<a<n. Once a factor a is found, we repeat the process with the complementary factor \frac{n}{a} until all the prime factors of n are found. This is simple in concept and is sure to produce the correct answer. For applications in cryptography, this brute force approach is essentially useless since the amount of time to try every candidate factor is prohibitively huge. The amount of time required may be more than the age of the universe if the brute force approach is used.

The brute force approach can be improved upon slightly by doing the trial divisions using candidate factors up to \sqrt{n}. It is well known that if a composite integer n is greater than one, then it has a prime divisor d such that 1<d \le \sqrt{n}. So instead of dividing n by every number a with 1<a<n, we can divide n by every prime number a with 1<a \le \sqrt{n}. But even this improved brute force approach will still take too long to be practical.

Let’s look at a quick example for brute force factoring. Let n=96638243. Note that \sqrt{n}=\sqrt{96638243}=9676. There are 1192 odd primes less than 9676. In dividing n by these primes, we stop at 127 and we have n=96638243=127 \cdot 737309. We now focus the attention on 737309. Note that \sqrt{737309}=858.67 and there are 147 odd primes less than 858. Dividing 737309 by these 147 candidate factors, we find that none of them is a factor. We can conclude 737309 is prime. Then we have the factorization n=96638243=127 \cdot 737309.

____________________________________________________________________________

Example of RSA

RSA is a public-key cryptosystem and is widely used for secure data transmission. The RSA public key consists of two parts. One is the modulus that is the product of two distinct prime factors. Suppose the modulus is called N and we have N=pq where p and q are distinct prime numbers. How large does N have to be? The larger the N is, the more secure RSA is. The current practice is that for corporate use the modulus is at least a 1024-bit number (the bit size is called the key length). If data is extra sensitive or if the data needs to be retained for a long time, then a larger key length should be used (e.g. 2048-bit). With a 1024-bit modulus N=pq, each prime factor is a 512-bit number. The other part of the RSA public key is the encryption key, which is an integer e that is relatively prime to the integer (p-1) \cdot (q-1).

Let’s say we want to generate a 1024-bit modulus. There are two challenges with a key of this size. One is that a reliable way is needed to obtain two prime numbers that are 512-bit long. Given a large integer that is at least 512-bit long, how do we determine reliably that it is prime? Is it possible to factor a 512-bit integer using the brute force approach? The other challenge is from the perspective of an attacker – successful factoring the 1024-bit modulus would break RSA and allow the attacker to read the secret message. Let’s look at the problem of the attacker trying to factor a 1024-bit number. A 1024-bit number is approximately 2^{1024}. The following calculation converts it to a decimal basis:

    \displaystyle 2^{1024}=(10^{\text{log(2)}})^{1024} \approx 10^{308.25}

We use \text{log}(x) to denote the logarithm of base 10. Note that 1024 \cdot \text{log}(2)=308.25. So a 1024-bit number has over 300 digits.

Let’s see what the challenge is if you want to factor a 1024-bit number. Suppose your chosen large number n is such that n \approx 10^{308}. Note that \sqrt{10^{308}}=10^{154}. According to the improved brute force approach described above, in effect you will need to divide n by every prime number less than 10^{154}.

Now let’s get an estimate on the number of prime numbers less than 10^{154}. According to the prime number theorem, the number of prime numbers at most x is approximately

    \displaystyle \pi(x) \approx \frac{x}{\text{ln}x}

where \pi(x) is the number of primes at most x. Then \pi(10^{154}) \approx 2.82 \cdot 10^{151}. This is certainly a lot of prime numbers to check.

It is hard to comprehend such large numbers. Let’s put this into perspective. Currently the world population is about 7 billion. Let’s say each person in the world possesses a supercomputer that can check 10^{40} prime numbers per second (i.e. to check whether they are factors of the number n). This scenario clearly far exceeds the computing resources that are currently available. Suppose that the 7 billion supercomputers are available and that each one can check 10^{40} many primes per second. Then in each second, the following is the number of prime numbers that can be checked by the 7 billion supercomputers.

    \displaystyle 7 \cdot 10^9 \cdot 10^{40}=7 \cdot 10^{49} \text{ prime numbers per second}

The following is the number of seconds it will take to check 2.82 \cdot 10^{151} many prime numbers:

    \displaystyle \frac{2.82 \cdot 10^{151}}{7 \cdot 10^{49}} \approx 4 \cdot 10^{101} \text{ seconds}

The universe is estimated to be about 13 billion years old. The following calculation converts it to seconds.

    13 \text{ billion years}=13 \cdot 10^9 \cdot 365 \cdot 24 \cdot 3600 \approx 4 \cdot 10^{17} \text{ seconds}

With 7 billion fast suppercomputers (one for each person in the world) running in the entire life of the universe, you can only finish checking

    \displaystyle \frac{4 \cdot 10^{17}}{4 \cdot 10^{101}}=\frac{1}{10^{84}}

of the 2.82 \cdot 10^{151} many prime numbers. Note that \frac{1}{10^{84}} is a tiny portion of 1%. So by taking the entire life of the universe to run the 7 billion supercomputers, each checking 10^{40} many candidate prime factors per second, you would not even make a dent in the problem!

The security of RSA rests on the apparent difficulty of factoring large numbers. If the modulus N=pq can be factored, then an eavesdropper can obtain the private key from the public key and be able to read the message. The difficulty in factoring means there is a good chance that RSA is secure. In order to break RSA, an attacker would probably have to explore other possible vulnerabilities instead of factoring the modulus.

By carrying out a similar calculation, we can also see that factoring a 512-bit number by brute force factoring is also not feasible. Thus in the RSA key generation process, it is not feasible to use factoring as a way to test primality. The alternative is to use efficient primality tests such as Fermat test or Miller-Rabin test. The computation for these tests is based on the fast powering algorithm, which is a very efficient algorithm.

____________________________________________________________________________

The story told by RSA numbers

The required time of more than the life of the universe as discussed above is based on the naïve brute force approach of factoring. There are many other factoring approaches that are much more efficient and much faster, e.g., the quadratic sieve algorithm, the number field sieve algorithm, and the general number field sieve algorithm. For these methods, with ample computing resources at the ready, factoring a 1024-bit or 2048-bit number may not take the entire life of the universe but make take decades or more. Even with these better methods, the disparity between slow factoring and fast primality testing is still very pronounced and dramatic.

The best evidence of slow factoring even with using modern methods is from the RSA numbers. The RSA numbers are part of the the RSA Factoring Challenge, which was created in 1991 to foster research in computational number theory and the practical difficulty of factoring large integers. The challenge was declared inactive in 2007. The effort behind the successful factorization of some of these numbers gives us an idea of the monumental challenges in factoring large numbers.

According to the link given in the above paragraph, there are 54 RSA numbers, ranging from 330 bits long to 2048 bits long (100 decimal digits to 617 decimal digits). Each of these numbers is a product of two prime numbers. Of these 54 numbers, 18 were successfully factored (as of the writing of this post). They were all massive efforts involving large groups of volunteers (in some cases using hundreds or thousands of computers), spanning over months or years. Some of methods used are the quadratic sieve algorithm, the number field sieve algorithm, and the general number field sieve algorithm.

The largest RSA number that was successfully factored is the RSA-768, which is 768 bits long and has 232 decimal digits (completed in December 2009). The method used was the Number Field Sieve method. There were 4 main steps in this effort. The first step is the polynomial selection, which took half a year using 80 processors. The second step is the sieving step, which took almost two years on many hundreds of machines. If only using a single core 2.2 GHz AMD Opteron processor with 2 GB RAM, the second step would take about 1500 years! The third step is the matrix step, which took a couple of weeks on a few processors. The final step took a few days, which involved a great deal of debugging.

The number field sieve method is the fastest known method for factoring large numbers that are a product of two primes (i.e. RSA moduli). The effort that went into factoring RSA-768 was massive and involved many years of complicated calculations and processing. This was only a medium size number on the list!

Another interesting observation that can be made is on the RSA numbers that have not been factored yet. There are 36 unfactored numbers in the list. One indication that RSA is secure in the current environment is that the larger numbers in the list are not yet factored (e.g. RSA-1024 which is 1024-bit long). Successful factorization of these numbers has important security implication for RSA. The largest number on the list is RSA-2048, which is 2048-bit long and has 617 digits. It is widely believed that RSA-2048 will stay unfactored in the decades to come, barring any dramatic and significant advance in computing technology.

The factoring challenge for the RSA numbers certainly provides empirical evidence that factoring is hard. Of course, no one should be complacent. We should not think that factoring will always be hard. Technology will continue to improve. A 768-bit RSA modulus was once considered secure. With the successful factorization of RSA-768, key size of 768 bits is no longer considered secure. Currently 1024 bit key size is considered secure. The RSA number RSA-1024 could very well be broken in within the next decade.

There could be new advances in factoring algorithm too. A problem that is thought to be hard may eventually turn out to be easy. Just because everyone thinks that there is no fast way of factoring, it does not mean that no such method exists. It is possible that someone has discovered such a method but decides to keep it secret in order to maintain the advantage. Beyond the issue of factoring, there could be some other vulnerabilities in RSA that can be explored and exploited by attackers.

____________________________________________________________________________

Fermat primality test

We now give some examples showing primality testing is a much better approach (over factoring) if the goal is to check the “prime or composite” status only. We use Fermat primality test as an example.

Example 1
Let n=15144781. This is a small number. So factoring would be practical as a primality test. We use it to illustrate the point that the “prime or composite” status can be determined without factoring. One option is to use Fermat’s little theorem (hence the name of Fermat primality test):

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

Consider the contrapositive of the theorem. If we can find an a, relatively prime to n such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we know for sure n is not prime. Such a value of a is said to be a Fermat witness for the compositeness of n.

If a Fermat witness is found, then we can say conclusively that n is composite. On the other hand, if a is relatively prime to n and a^{n-1} \equiv 1 \ (\text{mod} \ n), then n is probably a prime. We can then declare n is prime or choose to run the test for a few more random values of a.

The exponentiation a^{n-1} \ (\text{mod} \ n) is done using the fast powering algorithm, which involves a series of squarings and multiplications. Even for large moduli, the computer implementation of this algorithm is fast and efficient.

Let’s try some value of a, say a=2. Using an online calculator, we have

    2^{15144780} \equiv 1789293 \not \equiv 1 \ (\text{mod} \ 15144781)

In this case, one congruence calculation tells us that n=15144781 is not prime (if it were, the congruence calculation would lead to a value of one). It turns out that n=15144781 is a product of two primes where n=15144781=3733 \cdot 4057. Of course, this is not a secure modulus for RSA. The current consensus is to use a modulus that is at least 1024-bit long.

Example 2
Let n=15231691. This is also a small number (in relation what is required for RSA). Once again this is an illustrative example. We calculate a^{15231690} \ (\text{mod} \ 15231691) for a=2,3,4,5,6,7, the first few values of a. All such congruence values are one. We suspect that n=15231691 may be prime. So we randomly choose 20 values of a and compute a^{15231690} \ (\text{mod} \ 15231691). The following shows the results.

    \left[\begin{array}{rrr}      a & \text{ } & a^{n-1} \ \text{mod} \ n \\      \text{ } & \text{ } & n=15,231,691  \\      \text{ } & \text{ } & \text{ }  \\      3,747,236 & \text{ } & 1  \\      370,478 & \text{ } & 1  \\      12,094,560 & \text{ } & 1  \\      705,835 & \text{ } & 1  \\      10,571,714 & \text{ } & 1  \\      15,004,366 & \text{ } & 1  \\      12,216,046 & \text{ } & 1  \\        10,708,300 & \text{ } & 1  \\      6,243,738 & \text{ } & 1  \\      1,523,626 & \text{ } & 1  \\      10,496,554 & \text{ } & 1  \\      10,332,033 & \text{ } & 1  \\      10,233,123 & \text{ } & 1  \\      3,996,691 & \text{ } & 1  \\            4,221,958 & \text{ } & 1  \\      3,139,943 & \text{ } & 1  \\      1,736,767 & \text{ } & 1  \\      12,672,150 & \text{ } & 1  \\      12,028,143 & \text{ } & 1  \\      8,528,642 & \text{ } & 1    \end{array}\right]

For all 20 random values of a, a^{15231690} \equiv 1 \ (\text{mod} \ 15231691). This represents strong evidence (though not absolute proof) that n=15231691 is a prime. In fact, we can attach the following probability statement to the above table of 20 random values of a.

    If n=15231691 were a composite number that has at least one Fermat witness, there is at most a 0.0000953674% chance that 20 randomly selected values of a are not Fermat witnesses.

    In other words, if n=15231691 were a composite number that has at least one Fermat witness, there is at most a 0.0000953674% chance of getting 20 1’s in the above computation.

In general, if n has at least one Fermat witness, the probability that all k randomly selected values of a with 1<a<n are not Fermat witnesses is at most 0.5^k. For k=20, 0.5^{20}=0.000000953674, which is 0.0000953674%. The probability statement should give us enough confidence to consider n=15231691 a prime number.

There is a caveat that has to be mentioned. For the above probability statement to be valid, the number n must have at least one Fermat witness. If a number n is composite, we would like the test to produce a Fermat witness. It turns out that there are composite numbers that have no Fermat witnesses. These numbers are called Carmichael numbers. If n is such a number, a^{n-1} \equiv 1 \ (\text{mod} \ n) for any a that is relatively prime to the number n. In other words, the Fermat test will always indicate “probably prime” for Carmichael numbers. Unless you are lucky and randomly pick a value of a that shares a common prime factor with n, the Fermat test will always incorrectly identify a Carmichael number n as prime. Fortunately Carmichael numbers are rare, even though there are infinitely many of them. In this previous post, we estimate that a randomly selected 1024-bit odd integer has a less than one in 10^{88} chance of being a Carmichael number!

The Fermat test is a powerful test when the number being tested is a prime number or a composite number that has a Fermat witness. For Carmichael numbers, the test is likely to produce a false positive (identifying a composite number as prime). Thus the existence of Carmichael numbers is the biggest weakness of the Fermat test. Fortunately Carmichael numbers are rare. Though they are rare, their existence may still make the Fermat test unsuitable in some situation, e.g., when you test a number provided by your adversary. If you really want to avoid situations like these, you can always switch to the Miller-Rabin test.

____________________________________________________________________________

\copyright \ 2014 \text{ by Dan Ma}

An upper bound for Carmichael numbers

It is well known that Fermat’s little theorem can be used to establish the compositeness of some integers without actually obtaining the prime factorization. Fermat’s little theorem is an excellent test for compositeness as well as primality. However, there are composite numbers that evade the Fermat test, i.e. the Fermat test will fail to indicate that these composite integers are composite. These integers are called Carmichael numbers. However, Carmichael numbers are rare. We illustrate this point by doing some calculation using an upper bound for Carmichael numbers.

Let p be a prime number. According to Fermat’s little theorem, a^{p-1} \equiv 1 \ (\text{mod} \ p) for all integer a that is relatively prime to p (i.e., the GCD of a and p is 1). The Fermat primality test goes like this. Suppose that the “composite or prime” status of the positive integer n is not known. We randomly pick a number a \in \left\{2,3,\cdots,n-1 \right\}. If a is relatively prime to n and if a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we are certain that n is composite even though we may not know its prime factorization. Such a value of a is said to be a Fermat witness for (the compositeness of) a. If a^{n-1} \equiv 1 \ (\text{mod} \ n), then n is probably prime. But to be sure, repeat the calculation with more values of a. If the calculation is done for a large number of randomly selected values of a and if the calculation for every one of the values of a indicates that n is probably prime, we will have high confidence that n is prime. In other words, the probability of making a mistake is very small.

However here is a wrinkle in the Fermat test. There are composite numbers which have no Fermat witnesses. These numbers are called Carmichael numbers. Specifically a positive composite integer n is a Carmichael number if a^{n-1} \equiv 1 \ (\text{mod} \ n) for all a relatively prime to n. In other words, if n is a Carmichael number, the Fermat test always indicates n is probably prime no matter how many values of a you use in the test. Fortunately Carmichael numbers are rare. The upper bound discussed below gives an indication of why this is the case.

____________________________________________________________________________

An upper bound

For each positive integer n, let C(n) be the number of Carmichael numbers that are less than n. The following is an upper bound for C(n).

    \displaystyle C(n)<n \cdot \text{exp}\biggl(-\frac{(\text{ln} \ n) \ (\text{ln} \ \text{ln} \ \text{ln} \ n)}{\text{ln} \ \text{ln} \ n}  \biggr)

The formula is found here (credited to Richard G. E. Pinch). We use this upper bound to find out the chance of encountering a Carmichael numbers. As shown below, the upper bound can overestimate C(n). The main point we like to make is that even with the overestimation of Carmichael numbers represented by the above upper bound, the number of Carmichael number is extremely small in relation to n. This is even more so when n is large (e.g. a 1024-bit integer). Thus for a randomly selected 1024-bit odd number, the probability that it is a Carmichael number is practically zero (see Examples 4 and 5 below).

____________________________________________________________________________

Examples

Example 1
The first 10 Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341. Furthermore, there are only 16 Carmichael numbers less than 100,000. Let n=10^5. According to the above formula, the following is the upper bound for C(10^5):

    \displaystyle C(10^5)<10^5 \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^5) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^5)}{\text{ln} \ \text{ln} \ 10^5}  \biggr)=1485

The bound of 1485 is a lot more than the actual count of 16. Even with this inflated estimate, when you randomly select an odd positive integer less than 10,000, the probability of getting a Carmichael number is 0.0297. With the actual count of 16, the probability is 0.00032.

Example 2
Here’s another small example. There are only 2,163 Carmichael numbers that are less than 25,000,000,000. Let n=2.5 \cdot 10^{10}.

    \displaystyle C(2.5 \cdot 10^{10})<2.5 \cdot 10^{10} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 2.5 \cdot 10^{10}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 2.5 \cdot 10^{10})}{\text{ln} \ \text{ln} \ 2.5 \cdot 10^{10}}  \biggr)=4116019

This inflated bound is a more than 1900 times over the actual count of 2163. But even with this inflated bound, the probability of a random odd integer being Carmichael is under 0.00033 (about 3 in ten thousands). With the actual count of 2163, the probability is 0.00000017 (less than one in a million chance).

Example 3
Here’s a larger example. A calculation was made by Richard G. E. Pinch that there are 20,138,200 many Carmichael numbers up to 10^{21}. Let’s compare the actual probability and the probability based on the upper bound. The following is the upper bound of C(10^{21}).

    \displaystyle C(10^{21})<10^{21} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{21}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{21})}{\text{ln} \ \text{ln} \ 10^{21}}  \biggr) \approx 4.6 \cdot 10^{13}

The actual count of 20,138,200 is about 2 \cdot 10^{7}. So 4.6 \cdot 10^{13} is an inflated estimate. The following shows the probability of randomly selecting an odd integer that is Carmichael (both actual and inflated).

    \displaystyle \text{inflated probability}=\frac{4.6 \cdot 10^{13}}{0.5 \cdot 10^{21}}=\frac{4.6 \cdot 10^{13}}{5 \cdot 10^{20}}=\frac{0.92}{10^{7}} \approx \frac{1}{10.9 \cdot 10^6} <\frac{1}{10^6}

    \displaystyle \text{actual probability}=\frac{2 \cdot 10^{7}}{0.5 \cdot 10^{21}}=\frac{2 \cdot 10^{7}}{5 \cdot 10^{20}}=\frac{0.4}{10^{13}} = \frac{1}{25 \cdot 10^{12}} <\frac{1}{10^{12}}

Even with the inflated upper bound, the chance of randomly picking a Carmichael number is less than one in a million. With the actual count of 20,138,200, the chance of randomly picking a Carmichael number is less than one in a trillion!

Remark
The number 10^{21} is quite small in terms of real world applications. For example, in practice, the RSA algorithm requires picking prime numbers that are at least 512-bit long. The largest 512-bit numbers are approximately 10^{154}. What is the chance of randomly picking a Carmichael number in this range? First, let’s look at the Carmichael numbers up to the limit 10^{100}. Then we look at 10^{154}.

Example 4
Here’s the estimates for C(10^{100}) based on the above upper bound.

    \displaystyle C(10^{100})<10^{100} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{100}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{100})}{\text{ln} \ \text{ln} \ 10^{100}}  \biggr) \approx 7.3 \cdot 10^{68}

    \displaystyle \text{probability}=\frac{7.3 \cdot 10^{68}}{0.5 \cdot 10^{100}}=\frac{7.3 \cdot 10^{68}}{5 \cdot 10^{99}}=\frac{1.46}{10^{31}} \approx \frac{1}{6.8 \cdot 10^{30}} <\frac{1}{10^{30}}

Thus the chance of randomly picking a Carmichael number under 10^{100} is less than one in 10^{30}, i.e., practically zero.

Example 5
Here’s the example relevant to the RSA algorithm. As mentioned above, the RSA algorithm requires that the modulus in the public key is a product of two primes. The current practice is for the modulus to be at least 1024 bits. Thus each prime factor of the modulus is at least 512-bit. A 512-bit number can be as large as 10^{154} in decimal terms. When picking candidate for prime numbers, it is of interest to know the chance of picking a Carmichael number. We can get a sense of how small this probability is by asking: picking an odd integer under the limit 10^{154}, what is the chance that it is a Carmichael number? Here’s the estimates:

    \displaystyle C(10^{154})<10^{154} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{154}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{154})}{\text{ln} \ \text{ln} \ 10^{154}}  \biggr) \approx 3.7 \cdot 10^{107}

    \displaystyle \text{probability}=\frac{3.7 \cdot 10^{107}}{0.5 \cdot 10^{154}}=\frac{7.4}{10^{47}}=\frac{0.74}{10^{46}} < \frac{1}{10^{46}}

Thus a randomly selected odd integer under 10^{154} has a less than one in 10^{46} chance of being a Carmichael number!

Example 6
In some cases, for stronger security, the modulus in the RSA should be longer than 1024 bits, e,g, 2048 bits. If the modulus is a 2048-bit number, each prime in the modulus is a 1024-bit number. A 1024-bit number can be as large as 10^{308} in decimal terms. In picking an odd integer under the limit 10^{308}, what is the chance that it is a Carmichael number? Here’s the estimates:

    \displaystyle C(10^{308})<10^{308} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{308}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{308})}{\text{ln} \ \text{ln} \ 10^{308}}  \biggr) \approx 5 \cdot 10^{219}

    \displaystyle \text{probability}=\frac{5 \cdot 10^{219}}{0.5 \cdot 10^{308}}=\frac{5 \cdot 10^{219}}{5 \cdot 10^{307}} \approx \frac{1}{10^{88}}

Thus a randomly selected odd integer under 10^{308} has a less than one in 10^{88} chance of being a Carmichael number!

Remark
The above examples demonstrate that Carmichael numbers are rare. Even though the Fermat primality test “fails” for these numbers, the Fermat test is still safe to use because Carmichael numbers are hard to find. However, if you want to eliminate the error case of Carmichael numbers, you may want to consider using a test that will never misidentify Carmichael numbers. One possibility is to use the Miller-Rabin test.

____________________________________________________________________________

\copyright \ 2014 \text{ by Dan Ma}

Introducing Carmichael numbers

This is an introduction to Carmichael numbers. We first discuss Carmichael numbers in the context of Fermat primality test and then discuss several basic properties. We also prove Korselt’s criterion, which gives a useful characterization of Carmichael numbers.

___________________________________________________________________________________________________________________

Fermat Primality Test

Fermat’s little theorem states that if p is a prime number, then a^p \equiv a \ (\text{mod} \ p) for any integer a. Fermat primality test refers to the process of using Fermat little theorem to check the “prime vs. composite” status of an integer.

Suppose that we have a positive integer n such that the “prime vs. composite” status is not known. If we can find an integer a such that a^n \not \equiv a \ (\text{mod} \ n), then we know for certain that the modulus n is composite (or not prime). For example, let n = \text{8,134,619}. Note that 2^{8134619} \equiv 3024172 \ (\text{mod} \ 8134619). So we know right away that n = \text{8,134,619} is not prime, even though we do not know what its prime factors are just from applying this test.

Given a positive integer n, whenever a^n \not \equiv a \ (\text{mod} \ n), we say that a is a Fermat witness for (the compositeness of) the integer n. Thus 2 is a Fermat witness for n = \text{8,134,619}.

What if we try one value of a and find that a is not a witness for (the compositeness of) n? Then the test is inconclusive. The best we can say is that n is probably prime. It makes sense to try more values of a. If all the values of a we try are not witnesses for n (i.e. a^n \equiv a \ (\text{mod} \ n) for all the values of a we try), then it “seems likely” that n is prime. But if we actually declare that n is prime, the decision could be wrong!

Take n=\text{10,024,561}. For several randomly chosen values of a, we have the following calculations:

    \displaystyle 5055996^{10024561} \equiv 5055996 \ (\text{mod} \ 10024561)

    \displaystyle 4388786^{10024561} \equiv 4388786 \ (\text{mod} \ 10024561)

    \displaystyle 4589768^{10024561} \equiv 4589768 \ (\text{mod} \ 10024561)

    \displaystyle  146255^{10024561} \equiv 146255 \ (\text{mod} \ 10024561)

    \displaystyle 6047524^{10024561} \equiv 6047524 \ (\text{mod} \ 10024561)

The above calculations could certainly be taken as encouraging signs that n=\text{10,024,561} is prime. With more values of a, we also find that a^{10024561} \equiv a \ (\text{mod} \ 10024561). However, if we declare that n=\text{10,024,561} is prime, it turns out to be a wrong conclusion.

In reality, n=\text{10,024,561} is composite with \text{10,024,561}=71 \cdot 271 \cdot 521. Furthermore a^{10024561} \equiv a \ (\text{mod} \ 10024561) for any integer a. So there are no witnesses for n=\text{10,024,561}. Any composite positive integer that has no Fermat witnesses is called a Carmichael number, in honor of Robert Carmichael who in 1910 found the smallest such number, which is 561.

Fermat primality test is always correct if the conclusion is that the integer being tested is a composite number (assuming there is no computational error). If the test says the number is composite, then it must be a composite number. In other words, there are no false negatives in using Fermat primality test as described above.

On the other hand, there can be false positives as a result of using Fermat primality test. If the conclusion is that the integer being tested is a prime number, it is possible that the conclusion is wrong. For a wrong conclusion, it could be that there exists a witness for the number being tested and that we have missed it. Or it could be that the number being tested is a Carmichael number. Though Carmichael numbers are rare but there are infinitely many of them. So we cannot ignore them entirely. For these reasons, Fermat primality test as described above is often not used. Instead, other extensions of the Fermat primality test are used.

___________________________________________________________________________________________________________________

Carmichael Numbers

As indicated above, a Carmichael number is a positive composite integer that has no Fermat witnesses. Specifically, it is a positive composite integer that satisfies the conclusion of Fermat’s little theorem. In other words, a Carmichael number is a positive composite integer n such that a^n \equiv a \ (\text{mod} \ n) for any integer a.

Carmichael numbers are rare. A recent search found that there are \text{20,138,200} Carmichael numbers between 1 and 10^{21}, about one in 50 trillion numbers (documented in this Wikipedia entry on Carmichael numbers). However it was proven by Alford, Granville and Pomerance in 1994 that there are infinitely many Carmichael numbers (paper).

The smallest Carmichael number is 561=3 \cdot 11 \cdot 17. A small listing of Carmichael numbers can be found in this link, where the example of n=\text{10,024,561} is found.

Carmichael numbers must be odd integers. To see this, suppose n is a Carmichael number and is even. Let a=-1. By condition (1) of Theorem 1, we have (-1)^n=1 \equiv -1 \ (\text{mod} \ n). On the other hand, -1 \equiv n-1 \ (\text{mod} \ n). Thus n-1 \equiv 1 \ (\text{mod} \ n). Thus we have n \equiv 2 \ (\text{mod} \ n). It must be the case that n=2, contradicting the fact that n is a composite number. So any Carmichael must be odd.

The following theorem provides more insight about Carmichael numbers. A positive integer n is squarefree if its prime decomposition contains no repeated prime factors. In other words, the integer n is squarefree means that if \displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} is the prime factorization of n, then all exponents e_j=1.

    Theorem 1 (Korselt’s Criterion)

      Let n be a positive composite integer. Then the following conditions are equivalent.

      1. The condition a^n \equiv a \ (\text{mod} \ n) holds for any integer a.
      2. The condition a^{n-1} \equiv 1 \ (\text{mod} \ n) holds for any integer a that is relatively prime to n.
      3. The integer n is squarefree and p-1 \ \lvert \ (n-1) for any prime divisor p of n.

Proof of Theorem 1

1 \Longrightarrow 2
Suppose that a is relatively prime to the modulus n. Then let b be the multiplicative inverse of a modulo n, i.e., ab \equiv 1 \ (\text{mod} \ n). By (1), we have a^n \equiv a \ (\text{mod} \ n). Multiply both sides by the multiplicative inverse b, we have a^{n-1} \equiv 1 \ (\text{mod} \ n).

2 \Longrightarrow 3
Let \displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of n where p_i \ne p_j for i \ne j and each exponent e_j \ge 1. Since n must be odd, each p_j must be an odd prime.

We first show that each e_j=1, thus showing that n is squarefree. To this end, for each j, let a_j be a primitive root modulo p_j^{e_j} (see Theorem 4 in the post Primitive roots of powers of odd primes). Consider the following system of linear congruence equations:

    x \equiv a_1 \ (\text{mod} \ p_1^{e_1})

    x \equiv a_2 \ (\text{mod} \ p_2^{e_2})

      \cdots
      \cdots
      \cdots

    x \equiv a_t \ (\text{mod} \ p_t^{e_t})

Since the moduli p_j^{e_j} are pairwise relatively prime, this system must have a solution according to the Chinese Remainder Theorem (a proof is found here). Let a one such solution. For each j, since a_j is a primitive root modulo p_j^{e_j}, a_j is relatively prime to p_j^{e_j}. Since a \equiv a_j \ (\text{mod} \ p_j^{e_j}), a is relatively prime to p_j^{e_j} for each j. Consequently, a is relatively prime to n. By assumption (2), we have a^{n-1} \equiv 1 \ (\text{mod} \ n).

Now fix a j with 1 \le j \le t. We show that e_j=1. Since a^{n-1} \equiv 1 \ (\text{mod} \ n), a^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j}). Since a \equiv a_j \ (\text{mod} \ p_j^{e_j}), we have a_j^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j}). Note that the order of a_j modulo p_j^{e_j} is \phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1). Thus we have p_j^{e_j-1}(p_j-1) \ \lvert \ (n-1). If e_j>1, then p_j \ \lvert \ (n-1), which would mean that p_j \ \lvert \ 1. So it must be the case that e_j=1. It then follows that (p_j-1) \ \lvert \ (n-1).

3 \Longrightarrow 1
Suppose that n=p_1 p_2 \cdots p_t is a product of distinct prime numbers such that for each j, (p_j-1) \ \lvert \ (n-1).

Let a be any integer. First we show that a^n \equiv a \ (\text{mod} \ p_j) for all j. It then follows that a^n \equiv a \ (\text{mod} \ n).

Now fix a j with 1 \le j \le t. First consider the case that a and p_j are relatively prime. According to Fermat’s little theorem, a^{p_j-1} \equiv 1 \ (\text{mod} \ p_j). Since (p_j-1) \ \lvert \ (n-1), a^{n-1} \equiv 1 \ (\text{mod} \ p_j). By the Chinese Remainder Theorem, it follows that a^{n-1} \equiv 1 \ (\text{mod} \ n) and a^n \equiv a \ (\text{mod} \ n). \blacksquare

Examples
With Korselt’s criterion, it is easy to verify Carmichael numbers as long as the numbers are factored. For example, the smallest Carmichael number is 561=3 \cdot 11 \cdot 17. The number is obviously squarefree. furthermore 560 is divisible by 2, 10 and 16.

The number \text{10,024,561}= 71 \cdot 271 \cdot 521 is discussed above. We can also verify that this is a Carmichael number: 70 \ \lvert \ \text{10,024,560}, 270 \ \lvert \ \text{10,024,560} and 520 \ \lvert \ \text{10,024,560}.

Here’s three more Carmichael numbers (found here):

    \text{23,382,529} = 97 \cdot 193 \cdot 1249

    \text{403,043,257} = 19 \cdot 37 \cdot 43 \cdot 67 \cdot 199

    \text{154,037,320,009} = 23 \cdot 173 \cdot 1327 \cdot 29173

We end the post by pointing out one more property of Carmichael numbers, that Carmichael numbers must have at least three distinct prime factors. To see this, suppose that n=p \cdot q is a Carmichael number with two distinct prime factors p and q. We can express n-1 as follows:

    n-1=pq-1=(p-1)q+q-1

Since n is Carmichael, p-1 \ \lvert \ (n-1). So n-1=(p-1)w for some integer w. Plugging this into the above equation, we see that p-1 \ \lvert \ (q-1). By symmetry, we can also show that q-1 \ \lvert \ (p-1). Thus p=q, a contradiction. So any Carmichael must have at least three prime factors.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Proving Fermat’s Little Theorem

In working with the notion of congruence modulo m where m is a positive integer, one important calculation is finding the powers of a number a, i.e, the calculation a^n \equiv \ \text{mod} \ m. In one particular situation the calculation of interest is to identify the power n such that a^n \equiv 1 \ \text{mod} \ m. One elementary tool that can shed some light on this situation is the Fermat’s little theorem. This post is a self contained proof of this theorem.

After proving the theorem, we examine variations in the statements of the Fermat’s little theorem. There are some subtle differences among the variations. In one version of the Fermat’s little theorem (Theorem 4a below), the converse is not true as witnessed by the Carmichael numbers. In another version (theorem 4b below), the converse is true and gives a slightly better primality test (see Theorem 5 below) than the typical statement of the Fermat’s little theorem.

___________________________________________________________________________________________________________________

Example

Before discussing Fermat’s theorem and its proof, let’s look at an example. Let m=11, which is a prime number. Calculate the powers of a modulo m=11 for all a where 1 \le a \le m-1. Our goal is to look for a^n \equiv 1 \ \text{mod} \ 11.

First of all, if the goal is a^n \equiv 1 \ \text{mod} \ 11, then a cannot be 11 or a multiple of 11. Note that if a is a multiple of 11, then a^n \equiv 0 \ (\text{mod} \ 11) for any positive integer n. So we only need to be concerned with numbers a that are not multiples of m=11, i.e., numbers a that are not divisible by m=11.

Any number greater than 11 and is not divisible by 11 is congruent modulo eleven to one integer r in the range 1 \le r \le 10. So we only need to calculate a^n modulo 11 for 1 \le a \le 10. The following table displays the results of a^n modulo m=11.

    \displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9&a^{10}  \\\text{ }&\text{ }&\text{ }   \\ 1&1&1&1&1&1&1&1&1&1 \\ 2&4&8&5&10&9&7&3&6&1 \\ 3&9&5&4&1&3&9&5&4&1 \\ 4&5&9&3&1&4&5&9&3&1 \\ 5&3&4&9&1&5&3&4&9&1 \\ 6&3&7&9&10&5&8&4&2&1 \\ 7&5&2&3&10&4&6&9&8&1 \\ 8&9&6&4&10&3&2&5&7&1 \\ 9&4&3&5&1&9&4&3&5&1 \\ 10&1&10&1&10&1&10&1&10&1 \end{bmatrix}

The above table indicates that to get a^n \equiv 1, the power can stop at 10, one less than the modulus. According to Fermat’s theorem, this is always the case as long as the modulus is a prime number and as long as the base a is a number that is not divisible by the modulus.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

The following is a statement of the theorem.

Theorem 1 (Fermat’s Little Theorem)
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a with \text{GCD}(a,m)=1.

Note that \text{GCD}(a,b) refers to the greatest common divisor of the integers a and b. When \text{GCD}(a,b)=1, the integers a and b are said to be relatively prime. We also use the notation a \ \lvert \ b to mean that the integer a divides b without leaving a remainder.

In the discussion at the end of the above example, the base a is a number that is required to be not divisible by the modulus m. If the modulus m is a prime number, a is a number that is not divisible by the modulus m is equivalent to the condition \text{GCD}(a,m)=1. See the section called Variations below.

We will present below a formal proof of the theorem. The following example will make the idea of the proof clear. Let m=11. Let a=3. Calculate the following 10 numbers:

    a, 2a, 3a, 4a, 5a, 6a, 7a, 8a, 9a, 10a

For each of the above numbers, find the least residue modulo m=11. The following shows the results.

    \displaystyle \begin{aligned} \text{ }&1 \cdot 3 \equiv 3 \ \ (\text{mod} \ 11) \\&2 \cdot 3 \equiv 6 \ \ (\text{mod} \ 11) \\&3 \cdot 3 \equiv 9 \ \ (\text{mod} \ 11) \\&4 \cdot 3 \equiv 1 \ \ (\text{mod} \ 11) \\&5 \cdot 3 \equiv 4 \ \ (\text{mod} \ 11) \\&6 \cdot 3 \equiv 7 \ \ (\text{mod} \ 11) \\&7 \cdot 3 \equiv 10 \ \ (\text{mod} \ 11) \\&8 \cdot 3 \equiv 2 \ \  (\text{mod} \ 11) \\&9 \cdot 3 \equiv 5 \ \ (\text{mod} \ 11) \\&10 \cdot 3 \equiv 8 \ \  (\text{mod} \ 11) \end{aligned}

The above calculation shows that the least residues of a, 2a, 3a, 4a, 5a, 6a, 7a, 8a, 9a, 10a are just an rearrangement of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. So we have:

    a \cdot 2a \cdot 3a \cdot 4a \cdot 5a \cdot 6a \cdot 7a \cdot 8a \cdot 9a \cdot 10a \equiv 1 \cdot 2 \cdot  3 \cdot  4 \cdot  5 \cdot  6 \cdot  7 \cdot  8 \cdot  9 \cdot  10 \ \ (\text{mod} \ 11)

    a^{10} \ 1 \cdot 2 \cdot  3 \cdot  4 \cdot  5 \cdot  6 \cdot  7 \cdot  8 \cdot  9 \cdot  10 \equiv 1 \cdot 2 \cdot  3 \cdot  4 \cdot  5 \cdot  6 \cdot  7 \cdot  8 \cdot  9 \cdot  10 \ \ (\text{mod} \ 11)

Because 10! (10 factorial) is relatively prime with 11, we can cancel it out on both side of the congruence equation. Thus we have a^{10} \equiv 1 \ (\text{mod} \ 11) for a=3.

The above example has all the elements of the proof that we will present below. The basic idea is that whenever a and the modulus m are relatively prime, taking the least residues of a, 2a, 3a, \cdots, (m-1)a modulo m produces the numbers 1,2,3,\cdots,m-1 (possibly in a different order).

We have the following lemma.

Lemma 2
Let m be a prime number. Let a be a positive integer that is relatively prime with m, i.e., \text{GCD}(a,m)=1. Then calculating the least residues of the number a, 2a, 3a, \cdots, (m-1)a modulo m gives the numbers 1,2,3,\cdots,m-1.

Proof of Lemma 2

Let b_1,b_2,b_3,\cdots,b_{m-1} be the least residues of a, 2a, 3a, \cdots, (m-1)a modulo m. That is, for each j, b_j is the number with 0 \le b_j \le m-1 such that b_j \equiv j \cdot a \ (\text{mod} \ m). Our goal is to show that b_1,b_2,b_3,\cdots,b_{m-1} are the numbers 1,2,3,\cdots,m-1. To this end, we need to show that each b_j satisfies 1 \le b_j \le m-1 and that the numbers b_j are distinct.

First of all, b_j \ne 0. Suppose b_j=0. Then 0 \equiv j \cdot a \ (\text{mod} \ m) and m \lvert j \cdot a. By Euclid’s lemma, either m \ \lvert \ j or m \ \lvert \ a. Since \text{GCD}(a,m)=1, m \not \lvert \ a. So m \ \lvert \ j. But j is a positive integer less than m. So we have a contradiction. Thus each b_j satisfies 1 \le b_j \le m-1.

Now we show the numbers b_1,b_2,b_3,\cdots,b_{m-1} are distinct (the list has exactly m-1 numbers). To this end, we need to show that b_i \ne b_j when i \ne j. Suppose we have b_i=b_j and i \ne j. . Then i \cdot a \equiv j \cdot a \ (\text{mod} \ m). Since a and m are relatively prime, there is a cancelation law that allows us to cancel out a on both sides. Then we have i \equiv j \ (\text{mod} \ m). This means that m \ \lvert \ (i-j). Since i and j are positive integers less than the modulus m, for m \ \lvert \ (i-j) to happen, i must equals j, contradicting i \ne j. It follows that b_1,b_2,b_3,\cdots,b_{m-1} are distinct.

Taking stock of what we have so far, we have shown that \left\{b_1,b_2,b_3,\cdots,b_{m-1} \right\} \subset \left\{1,2,3,\cdots,m-1 \right\}. Both sides of the set inclusion have m-1 distinct numbers. So both sides of the set inclusion must equal. \blacksquare

We now prove Fermat’s little theorem.

Proof of Theorem 1

Let m be a prime number. Let a be a positive integer such that \text{GCD}(a,m)=1. By Lemma 2, the least resides of a, 2a, 3a, \cdots, (m-1)a modulo m are the numbers 1,2,3,\cdots,m-1. Thus we have the following congruence equations:

    a \cdot 2a \cdot 3a \cdots \cdot (m-1)a \equiv 1 \cdot 2 \cdot  3 \cdots \cdot  (m-1) \ \ (\text{mod} \ m)

    a^{m-1} \ 1 \cdot 2 \cdot  3 \cdots \cdot  (m-1) \equiv 1 \cdot 2 \cdot  3 \cdots   \cdot  (m-1) \ \ (\text{mod} \ m)

Just as in the earlier example, we can cancel out (m-1)! on both sides of the last congruence equation. Thus we have a^{m-1} \equiv 1 \ (\text{mod} \ m). \blacksquare

___________________________________________________________________________________________________________________

Variations

There are several ways to state the Fermat’s little theorem.

Theorem 3
If m is a prime number, then a^{m} \equiv a \ (\text{mod} \ m) for any integer a.

Theorem 3 is a version of the Fermat’s theorem that is sometimes stated instead of Theorem 1. It has the advantage of being valid for all integers a without having the need to consider whether a and the modulus m are relatively prime. It is easy to see that Theorem 3 implies Theorem 1. On the other hand, Theorem 3 is a corollary of Theorem 1.

To see that Theorem 3 follows from Theorem 1, let m be prime and a be any integer. Suppose a and the modulus m are not relatively prime. Then they have a common divisor d>1. Since m is prime, d must be m. So a is an integer multiple of m. Thus m divides both a and any power of a. We have a^{n} \equiv a \ (\text{mod} \ m) for any integer n. In particular, a^{m} \equiv a \ (\text{mod} \ m). The case that a and the modulus m are relatively prime follows from Theorem 1.

We now consider again the versions that deal with a^{m-1} \equiv 1. The following is a side-by-side comparison of Theorem 1 with another statement of the Fermat’s little theorem. Theorem 1 is re-labeled as Theorem 4a.

Theorem 4a (= Theorem 1)
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a with \text{GCD}(a,m)=1.

Theorem 4b
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a that is not divisible by m.

The equivalence of these two versions follows from the fact that for any prime number m, \text{GCD}(a,m)=1 if and only if a is not divisible by m. It is straightforward to see that if \text{GCD}(a,m)=1, then a is not divisible by m. For the converse to be true, m must be a prime number.

Since any integer a is congruent modulo m to some r with 0 \le r \le m-1, the following version is also an equivalent statement of the Fermat’s little theorem.

Theorem 4c
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a such that 1 \le a \le m-1.

___________________________________________________________________________________________________________________

The Converse

It is a natural question to ask whether the converse of the Fermat’s little theorem is true. In many sources, it is stated that the converse is not true. It turns out that the answer depends on the versions. The converse of Theorem 4a is not true, while the converse of Theorem 4b and the converse of Theorem 4c are true. Let’s compare the following statements about the positive integer m:

    a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a with \text{GCD}(a,m)=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

    a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a that is not divisible by m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Statement (1) is the conclusion of Theorem 4a, while statement (2) is the conclusion of Theorem 4b.

The statement (2) is a stronger statement. Any positive integer m that satisfies (2) would satisfy (1). This is because the set of all integers a for which \text{GCD}(a,m)=1 is a subset of the set of all integers a for which a is not divisible by m.

However, statement (1) does not imply statement (2). Any composite positive integer m that satisfies (1) is said to be a Carmichael number. Thus any Carmichael number would be an example showing that the converse of Theorem 4a is not true. There are infinitely many Carmichael numbers, the smallest of which is 561= 3 \cdot 11 \cdot 17. See the blog post Introducing Carmichael numbers for a more detailed discussion.

Any positive integer m satisfying statement (2) is a prime number. Thus the converse of Theorem 4b is true. We have the following theorem.

Theorem 5
Let m be an integer with m>1. Then m is a prime number if and only if statement (2) holds.

Proof of Theorem 5

The direction \Longrightarrow is Theorem 4b. To show \Longleftarrow, we show the contrapositive, that is, if m is not a prime number, then statement (2) does not hold, i.e., there is some a not divisible by m such that a^{m-1} \not \equiv 1 \ (\text{mod} \ m).

Suppose m is not prime. Then m has a divisor a where 1<a<m. We claim that a^{m-1} \not \equiv 1 \ (\text{mod} \ m). By way of a contradiction, suppose a^{m-1} \equiv 1 \ (\text{mod} \ m). Then m \ \lvert \ (a^{m-1}-1). Since a \ \lvert \ m, we have a \ \lvert \ (a^{m-1}-1). So a^{m-1}-1=a \cdot j for some integer j. Now we have a \cdot (a^{m-2}-j)=1. This implies that a divides 1. This is impossible since 1<a. This establishes the direction \Longleftarrow. \blacksquare

As a Carmichael number, 561 satisfies statement (1). However it would not satisfy statement (2). By the proof of Theorem 5, if a is a prime factor of 561, then a^{560} \not \equiv 1 \ (\text{mod} \ 561). Note that 3^{560} \not \equiv 1 \ (\text{mod} \ 561) since 3 is a divisor of 561. In fact, 3^{560} \equiv  375 \ (\text{mod} \ 561) and 11^{560} \equiv 154 \ (\text{mod} \ 561). We also have 17^{560} \equiv 34 \ (\text{mod} \ 561). Thus statement (1) is a weaker statement.

Any statement for the Fermat’s little theorem can be used as a primality test (Theorems 4a, 4b or 4c). On the face of it, Theorem 5 seems like an improvement over Theorem 4a, 4b or 4c since Theorem 5 can go both directions. However, using it to show that m is prime would require checking a^{m-1} \equiv 1 \ (\text{mod} \ m) for all a with 1 < a \le m-1. If m has hundreds of digits, this would be a monumental undertaking! Thus this primality test has its limitation both in terms of practical considerations and the possibility of producing false positives.

__________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Using Fermat’s Little Theorem to Test Primality

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 n is a prime number and if a is an integer that is relatively prime to n, then the following congruence relationship holds:

      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
    The test is to determine whether a large positive integer n is prime or composite. The test will output one of two results: n is Composite or n is 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
    Let n be a composite integer such that it is not a pseudoprime to at least one base (i.e. n has a Fermat witness). In other words, n is not a Carmichael number. Then n is not a pseudoprime to at least half of the bases a (1<a<n) that are relatively prime to n. In other words, n is a pseudoprime to at most half of the bases a (1<a<n) that are relatively prime to 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
    If b is a number such that 1<b<n and such that n is a pseudoprime to base b, then n is not a pseudoprime to base 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
    Let n be a composite integer such that it is not a pseudoprime to at least one base. Then n is not a pseudoprime to at least \displaystyle \frac{\phi(n)}{2} many bases in the interval 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.

Note:
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.

___________________________________________________________________
\copyright \ \ 2013 - 2015 \ \text{Dan Ma}