Large Carmichael numbers that are strong pseudoprimes to several bases

There is a very strong theorem in the paper [1] that has impactful theoretical results. For example, Theorem 1 in [1] implies that for any given finite set of bases, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the bases in the given finite set. Another implication of Theorem 1 of [1] is that there are infinitely many Carmichael numbers that have no small prime factors.

Given an odd number n whose “prime versus composite” status is not known, set n-1=2^k \cdot Q where k \ge 1 and Q is odd. The number n is said to be a probable prime to base a if the conclusion of Fermat’s little theorem holds, i.e., a^{n-1} \equiv 1 \ (\text{mod} \ n). A probable prime to base a could be prime or could be composite. If the latter, it is said to be a pseudoprime to base a.

The number n is said to be a strong probable prime to base a if a^{Q} \equiv 1 \ (\text{mod} \ n) or there exists some j=0,1,2,\cdots,k-1 such that a^{2^j \cdot Q} \equiv -1 \ (\text{mod} \ n). In other words, the number n is a strong probable prime to base a if in the following sequence

    a^Q, \ a^{2 \cdot Q}, \ a^{2^2 \cdot Q}, \cdots, \ a^{2^{k-1} \cdot Q}, a^{2^k \cdot Q} \ \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

the first term is a 1 or there exists a -1 followed by a 1. A strong probable prime to base a could be prime or could be composite. If the latter, it is said to be a strong pseudoprime to base a.

According to [6], there are only 4842 strong pseudoprimes to base 2 below 25 \cdot 10^9. Only 13 of these 4842 numbers are strong pseudoprimes to the bases 2, 3 and 5. The paper [4] has a listing of all strong pseudoprimes to the bases 2, 3 and 5 that are below 10^{12}. This listing has only 101 numbers. Only 9 these 101 numbers are strong pseudoprimes to bases 2, 3, 5 and 7. So there are indications that strong pseudoprimes are rare and that strong pseudoprimes to several bases are even rarer.

However, there are infinitely many strong pseudoprimes to a given base. In particular, there are infinitely many strong pseudoprimes to base 2 (two proofs are given in this previous post and in this previous post). According to what is said at the beginning of the post, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the first trillion prime bases! Furthermore, for these Carmichael numbers, any prime factors must be larger than the first trillion primes bases! It makes sense to examine this theorem so that we can further understand the implied results. The theorem is obviously a deep theoretical result, established by heavy duty machinery (theoretically speaking).

Fermat’s little theorem implies that if n happens to be a prime number, then n is a probable prime to all bases a that are relatively prime to n. It is easy to see that if n is a prime number, then n is a strong probable prime to all bases a that are relatively prime to n. Equivalently, if n is not a strong probable prime to some base a, then n is proved to be composite. Such a base a is said to be a witness for the compositeness of n. So a witness is a base, when used in the calculation for (1), will prove the compositeness of a number. Here’s one reason that the concept of strong pseudoprime is better than the concept of pseudoprime. If n is composite, there is at least one base that is a witness for n (see this previous post).

A Carmichael number is a composite number n such that it is a pseudoprime to all the bases relatively prime to n. Thus the Fermat test will never detect the compositeness of Carmichael numbers. On the other hand, the strong probable prime test (the Miller-Rabin test) will likely to give the correct result on Carmichael numbers.

Let n be an odd positive composite number. Let W(n) denote the smallest witness for the compositeness of n. Since any composite number has at least one witness, there is a least one. So W(n) is well defined. It is clear that W(n)>b if and only if n is a strong pseudoprime to all bases \le b. So any composite number that has a large least witness is a strong pseudoprime to many bases. The following is the statement of Theorem 1 of [1].

Theorem 1
There are infinitely many Carmichael numbers n such that

    \displaystyle W(n)> \text{ln}(n)^{\displaystyle \biggl[\frac{1}{3 \cdot \text{ln ln ln} \ n} \biggr]}=f(n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Furthermore, whenever x is sufficiently large, the number of such n below x is at least

    \displaystyle x ^{\displaystyle \biggl[\frac{1}{35 \cdot \text{ln ln ln} \ x}\biggr]}

We show how Theorem 2 is derived from Theorem 1.

Theorem 2
Given a finite set of bases, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the bases in the finite set.

Proof of Theorem 2
Consider the function f(n) defined in the right-hand side of the inequality (2) in the statement of Theorem 1. The key facts about this function are that:

  • The function f(n) is an increasing function for sufficiently large n.
  • The function f(n) is increasing without bound, i.e., for each sufficiently large N, there exists an n such that f(n)>N.

We use these two facts to derive the intended results. These two key facts will be discussed at the end. By Theorem 1, there exist Carmichael numbers

    n_1 < n_2 < n_3 < \cdots

such that (2) holds for each term in the sequence, i.e., W(n_j)>f(n_j) for each j. Based on the key facts, the following sequence is increasing without bound.

    f(n_1),f(n_2),f(n_3),\cdots

Let B be a finite set of positive integers \ge 2. Choose some k such that for each j>k, f(n_j) is greater than all elements of B. Let m be the maximum of all the integers in the finite set B. Now it is clear that for each j>k, f(n_j)>m and that W(n_j)>m. It follows that for each of the following infinitely many Carmichael numbers

    n_{k+1} < n_{k+1} < n_{k+3} < \cdots

the least witness is greater than m. Thus all these Carmichael numbers are strong psuedoprimes to all bases \le m, hence to all the bases in the finite set B.

To see that the function f(n) is increasing pass some sufficiently large n, take the derivative of \text{ln} f(n).

    \displaystyle \text{ln} f(n)=\frac{\text{ln} \ n}{3 \ \text{ln ln ln} \ x}

    \displaystyle \begin{aligned} (\text{ln} f(n))^{'}&=\frac{3 \ \text{ln ln ln} \ n \ \displaystyle \frac{1}{n} - (\text{ln} \ n) \ 3 \ \displaystyle \frac{1}{\text{ln ln} \ n} \ \frac{1}{\text{ln} \ n} \ \frac{1}{n}}{(3 \ \text{ln ln ln} \ x)^2} \\&\text{ } \\&=\frac{ \displaystyle \frac{3 \ \text{ln ln ln} \ n}{n} - \displaystyle \frac{3}{n \ \text{ln ln} \ n} }{(3 \ \text{ln ln ln} \ x)^2} \\&\text { }\\&=\frac{3 \ (\text{ln ln ln} \ n) \ (\text{ln ln} \ n) - 3}{n \ \text{ln ln} \ n \ (3 \ \text{ln ln ln} \ x)^2}  \end{aligned}

The above derivative is positive if and only if the following is true:

    (\text{ln ln ln} \ n) \ (\text{ln ln} \ n) >1

This last inequality always holds for sufficiently large n. Thus for sufficiently large n, the derivative of f(n) is positive, meaning that f(n) is increasing.

To see that f(n) increases without bound, fix a sufficiently large N. Choose an integer j large enough such that e^j > N and e^j > 3j^2. Let n=e^k where \displaystyle k=e^{\displaystyle (e^{j})}. We have the following.

    \displaystyle \begin{aligned} f(n)&= f(e^k) \\&=k^{\displaystyle \biggl[\frac{1}{3 \ \text{ln ln \ k}}\biggr]} \\&=(e^{\displaystyle (e^{j})})^{\displaystyle \frac{1}{3j}} \\&=\displaystyle e^{\displaystyle \frac{e^j}{3j}} \\&>\displaystyle e^{\displaystyle \frac{3j^2}{3j}}=e^j>N  \end{aligned}

The above derivation shows that the function f(n) increases without bound. \blacksquare

Theorem 2 implies the following theorem. For the infinitely many Carmichael numbers that are strong pseudoprimes to all the bases below a bound, no prime numbers within the bound can be a factor for these Carmichael numbers.

Theorem 3
There are infinitely many Carmichael numbers that have no small prime factors.

The Carmichael numbers that are claimed to exist by Theorem 3 will likely not be detected as composite by factoring. For example, consider a Carmichael number that is a strong pseudoprime to all the prime bases below 2^{1024}. Its compositeness will likely not be detected by factoring based on the current computing technology and on the current factoring algorithms. This is another reason that the strong probable prime test (the Miller-Rabin test) is better than the Fermat test. The latter will declare the Carmichael number in question as prime while the former will likely be correct.

___________________________________________________________________

Example

Consider the following 397-digit number.

    C=
    28871482380507712126714295971303939919776094592797
    22700926516024197432303799152733116328983144639225
    94197780311092934965557841894944174093380561511397
    99994215424169339729054237110027510420801349667317
    55152859226962916775325475044445856101949404200039
    90443211677661994962953925045269871932907037356403
    22737012784538991261203092448414947289768854060249
    76768122077071687938121709811322297802059565867

The above is a 397-digit Carmichael number found in [3]. It is a strong pseudoprime to all the prime bases up to 300. According to Theorem 2, there are infinitely many other Carmichael numbers that are strong pseudoprimes to all the prime bases below 300. The number C is generated using the following formula.

    C=p_1 [313(p_1-1)+1] [353(p_1-1)+1]

    p_1=
    29674495668685510550154174642905332730771991799853
    04335099507553127683875317177019959423859642812118
    8033664754218345562493168782883

___________________________________________________________________

Reference

  1. Alford W., Granville A., and Pomerance C., On the difficulty of finding reliable witnesses, L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory: Proc. ANTS-I, Ithaca, NY, volume 877 of Lecture Notes in Computer Science, pages 1–16. Springer–Verlag, 1994.
  2. Alford W., Granville A., and Pomerance C., There are infinitely many Carmichael numbers, Ann. of Math. 139, 703-722, 1994.
  3. Arnault F., Constructing Carmichael numbers which are pseudoprimes to several bases, J. Symbolic Computation, 20, 151-161, 1995.
  4. Jaeschke G., On strong pseudoprimes to several bases, Math. Comp., Volume 61, No. 204, 915-926, 1993.
  5. Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
  6. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to 25 \cdot 10^9, Math. Comp., Volume 35, 1003-1026, 1980.

___________________________________________________________________
\copyright \ \ 2014 \ \text{Dan Ma}

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s