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}

Advertisements

6 thoughts on “An upper bound for Carmichael numbers

  1. Pingback: Factorization versus primality testing | Exploring Number Theory

  2. Pingback: Counting Fermat witnesses | Exploring Number Theory

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

  4. Pingback: Probable primes and pseudoprimes | Mathematical Cryptography

  5. Pingback: The Fermat primality test | Mathematical Cryptography

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