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 be a prime number. According to Fermat’s little theorem, for all integer that is relatively prime to (i.e., the GCD of and is 1). The Fermat primality test goes like this. Suppose that the “composite or prime” status of the positive integer is not known. We randomly pick a number . If is relatively prime to and if , then we are certain that is composite even though we may not know its prime factorization. Such a value of is said to be a Fermat witness for (the compositeness of) . If , then is probably prime. But to be sure, repeat the calculation with more values of . If the calculation is done for a large number of randomly selected values of and if the calculation for every one of the values of indicates that is probably prime, we will have high confidence that 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 is a Carmichael number if for all relatively prime to . In other words, if is a Carmichael number, the Fermat test always indicates is probably prime no matter how many values of 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 , let be the number of Carmichael numbers that are less than . The following is an upper bound for .

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 . 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 . This is even more so when 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 . According to the above formula, the following is the upper bound for :

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

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 . Let’s compare the actual probability and the probability based on the upper bound. The following is the upper bound of .

The actual count of 20,138,200 is about . So is an inflated estimate. The following shows the probability of randomly selecting an odd integer that is Carmichael (both actual and inflated).

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 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 . 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 . Then we look at .

**Example 4**

Here’s the estimates for based on the above upper bound.

Thus the chance of randomly picking a Carmichael number under is less than one in , 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 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 , what is the chance that it is a Carmichael number? Here’s the estimates:

Thus a randomly selected odd integer under has a less than one in 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 in decimal terms. In picking an odd integer under the limit , what is the chance that it is a Carmichael number? Here’s the estimates:

Thus a randomly selected odd integer under has a less than one in 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.

____________________________________________________________________________

Pingback: Factorization versus primality testing | Exploring Number Theory

Pingback: Counting Fermat witnesses | Exploring Number Theory

Pingback: A primality testing exercise from RSA-100 | Mathematical Cryptography

Pingback: Probable primes and pseudoprimes | Mathematical Cryptography

Pingback: The Fermat primality test | Mathematical Cryptography

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