# 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}$

# A primality proving algorithm using least strong pseudoprimes

This post is the continuation of this previous post. In this post, we discuss a deterministic primality proving algorithm that uses the least strong pseudoprimes to several prime bases. After describing the test, we present several examples.

The previous post discusses the notion of witness for the strong probable prime test (the Miller-Rabin test). One important characteristic of the strong probable prime test is that for any composite number, there is always at least one witness (in fact lots of them). This means that the strong probable prime test is not going to be tripped up on a Carmichael number like it is for the Fermat test.

When there is a guarantee that every composite number has a witness for its compositeness, it makes sense to talk about the least witness $w(n)$ for a composite number $n$. The statement that $w(n)>B$ is equivalent to the statement that $n$ is a strong pseudoprime to all the bases less than or equal to $B$. Strong pseudoprimes to base 2 are rare. Strong pseudoprimes to multiple bases are even rarer. According to [2], there are only 13 numbers below $25 \cdot 10^9$ that are strong pseudoprimes to all of the bases 2, 3 and 5. Thus it is rare to have composite numbers $n$ whose $w(n)>5$. Because they are rare, knowing about strong pseudoprimes can help us find the primes.

The test in question comes from [1]. It had been improved and sharpened over the years. The paper [1] seems to contain the best results to date regarding this test. To see how the method evolved and got improved, any interested reader can look at the references provided in [1]. Let $\psi_n$ be the least strong pseudoprime to all of the first $n$ prime bases. The paper [1] presents the following 11 least strong pseudoprimes.

$\psi_1=$ 2047

$\psi_2=$ 1373653

$\psi_3=$ 25326001

$\psi_4=$ 3215031751

$\psi_5=$ 2152302898747

$\psi_6=$ 3474749660383

$\psi_7=\psi_8=$ 341550071723321

$\psi_9=\psi_{10}=\psi_{11}=$ 3825123056546413051

To illustrate, the number 25326001 is the smallest strong pseudoprime to all the bases 2, 3 and 5. For any odd number $n$ less than 25326001, check whether $n$ is a strong probable to these 3 bases. If it is, then $n$ has to be prime. Otherwise, $n$ is a strong pseudoprime to bases 2, 3 and 5 that is less than 25326001! Of course, if $n$ happens to be not a strong probable prime to one of the 3 bases, then it is a composite number.

The test using $\psi_n$ represents a primality test that actually proves primality rather than just giving strong evidence for primality. Using $\psi_n$, the test only requires $n$ modular exponentiations. This test is a limited test since it only applies to numbers less than $\psi_n$. However, it is interesting to note that the notions of strong probable primes and strong pseudoprimes give a deterministic primality test (though limited) that is fast and easy to use in addition to the usual Miller-Rabin probabilistic primality test.

___________________________________________________________________

Examples

Example 1
Consider the number $n=$ 2795830049. This number is below $\psi_4$. So we check for probable primality of $n$ to the bases 2, 3, 5, and 7. First of all, $n-1=2^5 \cdot Q$ where $Q=$ 87369689. Here’s the calculation.

$2^Q \equiv 937249258 \ (\text{mod} \ 2795830049)$

$2^{2 \cdot Q} \equiv 2693069488 \ (\text{mod} \ 2795830049)$

$2^{4 \cdot Q} \equiv 226823779 \ (\text{mod} \ 2795830049)$

$2^{8 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)$

$2^{16 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)$

$2^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)$

Note that the first term that is a 1 in the above sequence is $2^{16 \cdot Q}$. The preceding term is a -1. Thus $n=$ 2795830049 is a strong probable prime to base 2. Now the base 3 calculation.

$3^Q \equiv 268289123 \ (\text{mod} \ 2795830049)$

$3^{2 \cdot Q} \equiv 717416975 \ (\text{mod} \ 2795830049)$

$3^{4 \cdot Q} \equiv 17652213 \ (\text{mod} \ 2795830049)$

$3^{8 \cdot Q} \equiv 2569006270 \ (\text{mod} \ 2795830049)$

$3^{16 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)$

$3^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)$

Note that the first term that is a 1 in the above sequence is the last term $3^{32 \cdot Q}$. The preceding term is a -1. Thus $n=$ 2795830049 is a strong probable prime to base 3. Now the base 5 calculation.

$5^Q \equiv 102760561 \ (\text{mod} \ 2795830049)$

$5^{2 \cdot Q} \equiv 226823779 \ (\text{mod} \ 2795830049)$

$5^{4 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)$

$5^{8 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)$

$5^{16 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)$

$5^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)$

The base 7 calculation.

$7^Q \equiv 121266349 \ (\text{mod} \ 2795830049)$

$7^{2 \cdot Q} \equiv 937249258 \ (\text{mod} \ 2795830049)$

$7^{4 \cdot Q} \equiv 2693069488 \ (\text{mod} \ 2795830049)$

$7^{8 \cdot Q} \equiv 226823779 \ (\text{mod} \ 2795830049)$

$7^{16 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)$

$7^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)$

Both the base 5 and base 7 calculations show that $n=$ 2795830049 is a strong probable prime to both bases. The calculations for the 4 bases conclusively prove that $n=$ 2795830049 is a prime number.

Example 2
Consider the number $n=$ 62834664835837. This number is below $\psi_7$. So we check for probable primality to the bases 2, 3, 5, 7, 11, 13, and 17. First, $n-1=2^2 \cdot Q$ where $Q=$ 15708666208959.

$2^Q \equiv 49994720924726 \ (\text{mod} \ 62834664835837)$

$2^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)$

$2^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

__________________

$3^Q \equiv 1 \ (\text{mod} \ 62834664835837)$

$3^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

$3^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

__________________

$5^Q \equiv 49994720924726 \ (\text{mod} \ 62834664835837)$

$5^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)$

$5^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

__________________

$7^Q \equiv 49994720924726 \ (\text{mod} \ 62834664835837)$

$7^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)$

$7^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

__________________

$11^Q \equiv 1 \ (\text{mod} \ 62834664835837)$

$11^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

$11^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

__________________

$13^Q \equiv 12839943911111 \ (\text{mod} \ 62834664835837)$

$13^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)$

$13^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

__________________

$17^Q \equiv 1 \ (\text{mod} \ 62834664835837)$

$17^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

$17^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)$

The calculation for all bases shows that $n=$ 62834664835837 is a strong probable primes to all 7 prime bases. This shows that $n=$ 62834664835837 is prime.

Example 3
Consider the number $n=$ 21276028621. This is a 11-digit number and is less than $\psi_5$. The algorithm is to check for the strong probable primality of $n$ to the first 5 prime bases – 2, 3, 5, 7, 11. First, $n-1=2^2 \cdot Q$ where $Q=$ 5319007155.

$2^Q \equiv 560973617 \ (\text{mod} \ 21276028621)$

$2^{2 \cdot Q} \equiv 21276028620 \equiv -1 \ (\text{mod} \ 21276028621)$

$2^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)$

__________________

$3^Q \equiv 1 \ (\text{mod} \ 21276028621)$

$3^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)$

$3^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)$

__________________

$5^Q \equiv 1 \ (\text{mod} \ 21276028621)$

$5^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)$

$5^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)$

__________________

$7^Q \equiv 10282342854 \ (\text{mod} \ 21276028621)$

$7^{2 \cdot Q} \equiv 19716227277 \ (\text{mod} \ 21276028621)$

$7^{4 \cdot Q} \equiv 21275616058 \ (\text{mod} \ 21276028621)$

Things are going well for the first 3 prime bases. The number $n=$ 21276028621 is a strong pseudoprime to the first 3 prime bases. However, it is not a strong probable prime to base 7. Thus the number is composite. In fact, $n=$ 21276028621 is one of the 13 numbers below $25 \cdot 10^9$ that are strong pseudoprimes to bases 2, 3 and 5.

___________________________________________________________________

Exercises

Use the least strong pseudoprime primality test that is described here to determine the primality or compositeness of the following numbers:

• 58300313
• 235993423
• 1777288949
• 40590868757
• 874191954161
• 8667694799429
• 1250195846428003

___________________________________________________________________

Reference

1. Yupeng Jiang, Yingpu Deng, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
2. 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}$

# Looking for a good witness

For some primality tests, the approach of proving a number as composite is to produce an auxiliary number that shows that a property of prime numbers is violated. Such an auxiliary number is called a “witness” for compositeness. When using such a primality test on a composite number, for the test to be correct, at least one “witness” must be found. In this post, we compare the Fermat primality test and the Miller-Rabin test from the standpoint of producing “witnesses”. In this regard, the Fermat test works correctly most of the time. But there is a rare but infinite class of composite numbers for which no Fermat test witness can be found. On the other hand, using the Miller-Rabin test on a composite number, at least one witness can be found (in fact, there are lots of them).

___________________________________________________________________

Fermat witnesses

According to Fermat’s little theorem, if $n$ is a prime number, then the following congruence holds for all numbers $a$ that are coprime to $n$.

$\displaystyle a^{n-1} \equiv 1 \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

If there exists a number $a$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$, then $n$ is proved to be composite, in which case the number $a$ is said to be a Fermat witness for the compositeness of $n$. If the congruence (1) holds for several values of $a$, then $n$ is a likely a prime.

Suppose $n$ is a large odd number whose “prime versus composite” status is not known. If the congruence (1) holds for some positive integer $a$, then $n$ is said to be a probable prime to base $a$. A probable prime to the base $a$ could be prime or could be composite. If the latter, the number $n$ is said to be a pseudoprime to base $a$.

This is how the Fermat test (or probable prime test) works. Given that $n$ is a large odd number whose “prime versus composite” status is not known, if $n$ is not a probable prime to one base $a$, then $n$ is proven to be composite and $a$ is a Fermat witness for $n$. On the other hand, if $n$ is a probable prime to several randomly selected bases, then $n$ is a probable prime.

Suppose that you apply the Fermat test on the number $n$ and find that $n$ is a probable prime to several bases. There are two possibilities. Either $n$ is prime or is a pseudoprime to the several bases that are being used. Pseudoprimess to one base are rare. Pseudoprimes to several bases at once are even rarer. For example, according to [3], there are only 21853 pseudoprimes to the base 2 that are less than $25 \cdot 10^9$. The number of primes below $25 \cdot 10^9$ is roughly $10^9$. So most probable primes to base 2 are primes. Of the 21853 pseudoprimes to the base 2 that are below $25 \cdot 10^9$, 4709 of them are pseudoprimes to the bases 2 and 3, 2522 of them are pseudoprimes to the bases 2, 3 and 5, and 1770 of them are pseudoprimes to the bases 2, 3, 5 and 7. Thus there is indication that the numbers that are pseudoprimes to several bases are very rare. Therefore, the number $n$ being a simultaneous pseudoprime to several bases is very strong evidence that $n$ is prime. But this is not the end of the story for the Fermat test.

The Fermat test can detect the compositeness of most composite numbers. These are the numbers $n$ that are probable prime to one base but are not probable prime to another base. For example, 341 is a probable prime to base 2 since $2^{340} \equiv 1 \ (\text{mod} \ 341)$. On the other hand, $3^{340} \equiv 56 \ (\text{mod} \ 341)$. Thus 341 is not a probable prime to base 3 (i.e. 3 is a Fermat witness for the compositeness of 341). For integers like 341, they may be probable primes to one base, but they are not probable primes to another base. If there exists at least one Fermat witness for a composite number, there is a good chance that the Fermat test will detect the compositeness.

A odd composite number $n$ is said to be a Carmichael number if the congruence (1) holds for all numbers $a$ coprime to $n$. The smallest Carmichael number is 561. There is no danger of mistaking a small Carmichael number such as 561 as prime because factoring is possible. Carmichael numbers are rare but there are infinitely of them. So there are large Carmichael numbers (e.g. with hundreds of digits or thousands of digits). The Fermat test fails completely with these large Carmichael numbers. In other words, no matter how many bases are used, it is impossible to find a number $a$ that will witness the compositeness of a Carmichael number. Unlike the number 341, the Fermat test will fail to detect the compositeness of a Carmichael number.

___________________________________________________________________

Looking for a better type of witness

Let $n$ be an odd number with $n-1=2^k \cdot Q$ where $k \ge 1$ and $Q$ is odd. Then compute the following sequence of $k+1$ numbers modulo $n$:

$\displaystyle a^Q, \ a^{2Q}, \ a^{2^2 Q}, \ \cdots, \ a^{2^{k-1} Q}, \ a^{2^{k} Q} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

where $a$ is some number coprime to $n$. The first term in the sequence can be calculated by using the fast powering algorithm. Each subsequent term is the square of the preceding one. Of course, the last term is the same as $a^{n-1}$, the calculation for (1). Then if this calculation is done on a prime number $n$, the last term in (2) is always a 1. But more can be said about the sequence (2).

The better witnesses and primality test we discuss here are based on this theorem about prime numbers.

If $n$ is a prime number, then either one of the following conditions holds:

• $\displaystyle a^{Q} \equiv 1 \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2a)$
• $\displaystyle a^{2^j \cdot Q} \equiv -1 \ (\text{mod} \ n)$ for some $j=0,1,2,\cdots, k-1 \ \ \ \ \ \ \ \ (2b)$

$\text{ }$

for each number $a$ that is coprime to $n$.

The theorem just mentioned is the basis of the Miller-Rabin test. If there exists some $a$ such that both (2a) and (2b) are not true, then the number $n$ is proved to be composite, in which case the number $a$ is said to be a witness for the compositeness of $n$. So a witness from the Fermat test standpoint is called Fermat witness. The term witness here refers to the calculation of (2). If the conditions (2a) or (2b) holds for several values of $a$, then $n$ is likely a prime number.

Suppose $n$ is a large odd number whose “prime versus composite” status is not known. If the conditions (2a) or (2b) holds for some positive integer $a$, then $n$ is said to be a strong probable prime to base $a$. A strong probable prime to the base $a$ could be prime or could be composite. If the latter, the number $n$ is said to be a strong pseudoprime to base $a$.

This is how the Miller-Rabin test (or strong probable prime test) works. Given that $n$ is a large odd number whose “prime versus composite” status is not known, if $n$ is not a strong probable prime to one base $a$, then $n$ is proved to be composite and the number $a$ is a witness for $a$. If $n$ is a strong probable prime to several randomly chosen bases, then the probability that $n$ is composite is smaller than $4^{-k}$ (if $k$ bases are used). In other words, the error probability can be made arbitrarily small by using more random bases in the calculation for sequence (2).

The last point about the small error probability is the most important advantage of the Miller-Rabin test over the Fermat test. Let’s look at a small example first. Recall that 561 is the smallest Carmichael number. Note that $560=2^4 \cdot 35$. The following is the calculation for (2).

$2^{35} \equiv 263 \ (\text{mod} \ 561)$

$2^{2 \cdot 35} \equiv 166 \ (\text{mod} \ 561)$

$2^{4 \cdot 35} \equiv 67 \ (\text{mod} \ 561)$

$2^{8 \cdot 35} \equiv 1 \ (\text{mod} \ 561)$

$2^{16 \cdot 35} \equiv 1 \ (\text{mod} \ 561)$

The number 561 is a probable prime to base 2 (from a Fermat perspective). Notice that the condition (2a) is not met. The condition (2b) is also not met since the term preceding the first 1 is 67, which is not congruent to -1. So the number 2 is a witness for the compositeness of 561. The Fermat test will have virtually no chance of detecting the compositeness of 561. Yet the strong probable prime test takes only one calculation for 561. In this case at least, it is pretty easy to find a witness.

___________________________________________________________________

At least one witness can be found

One characteristic of the strong probable prime test is that there are lots of witnesses when testing composite numbers. In fact, if $n$ is a composite number, over 75% of the possible choices of bases $a$ are witnesses for $n$. We prove a simpler theorem that if $n$ is composite, at least one witness for the compositeness of $n$ can be found. Even this much weaker theorem is a big improvement over the Fermat test.

Theorem 1
Let $n$ be a composite positive odd number. Then there a number $a$ that is coprime to $n$ such that $n$ is not a strong pseudoprime to base $a$.

Proof of Theorem 1
Let $n=u \cdot v$ such that $u,v$ are odd and are coprime. Consider the following two congruence equations.

$x \equiv 1 \ (\text{mod} \ u)$

$x \equiv -1 \ (\text{mod} \ v)$

By the Chinese remainder theorem (CRT), there is an $a$ such that

$a \equiv 1 \ (\text{mod} \ u)$

$a \equiv -1 \ (\text{mod} \ v)$

We can assume that $1. If not, reduce $a$ modulo $n$. Then $a \not \equiv 1 \ (\text{mod} \ n)$. If $a \equiv 1 \ (\text{mod} \ n)$, then $a=1+n \cdot t=1+u \cdot v \cdot t$ for some $t$. This would mean that $a \equiv 1 \ (\text{mod} \ v)$, contradicting $a \equiv -1 \ (\text{mod} \ v)$. Similarly $a \not \equiv -1 \ (\text{mod} \ n)$. So we have $a \not \equiv \pm 1 \ (\text{mod} \ n)$. On the other hand, we have

$a^2 \equiv 1 \ (\text{mod} \ u)$

$a^2 \equiv 1 \ (\text{mod} \ v)$

By CRT, $a^2 \equiv 1 \ (\text{mod} \ n)$. Let $n-1=2^k \cdot Q$ where $k \ge 1$ and $Q$ odd. Let $Q=2w+1$ for some integer $w$. The following calculates $a^Q$ and $a^{2 \cdot Q}$.

$a^Q=a^{2w} \cdot a = (a^2)^w \cdot a \equiv 1^w \cdot a \equiv a \not \equiv \pm 1 \ (\text{mod} \ n)$

$a^{2 \cdot Q} \equiv (a^2)^Q \equiv (1)^Q \equiv 1 \ (\text{mod} \ n)$

The first term in (2) that is a 1 is $a^{2 \cdot Q}$. The preceding term is not a -1. This shows that the composite number $n$ is not a strong pseudoprime to base $a$. Thus for any composite number $n$, there always exists a witness for the compositeness of $n$. $\blacksquare$

The proof of Theorem 1 is essentially that if $n$ is composite, there is a square root other than $\pm 1$. This nontrivial square root is a witness to the compositeness of $n$.

___________________________________________________________________

The least witness

If $n$ is a composite number, there exists a witness for $n$ according to Theorem 1. Of all the witnesses for a given composite number $n$, there must be the smallest one. Let $w(n)$ be the least witness for the compositeness for the composite number $n$. The number $w(n)$ is an interesting one.

In general, the larger $w(n)$ is, the harder to find the number $n$. This stems from the fact that strong pseudoprimes are very rare. Most composite numbers are not strong pseudoprimes to base 2. For these composite numbers, $w(n)=2$. For the strong pseudoprimes to base 2, $w(n)>2$. For $w(n)>3$, the composite numbers must be strong pseudoprimes to base 2 and base 3. For $w(n)>5$, the composite numbers must be strong pseudoprimes to the prime bases 2, 3 and 5. There are only 13 such numbers below $25 \cdot 10^9$. Thus it is not easy to find composite numbers that have large least witnesses.

Two more comments to make. One is that knowing the least integer $n$ such that $w(n)$ is greater than the first $k$ prime numbers can be as a deterministic primality test [2]. This is discussed in the next post. The other is that even though a large $w(n)$ means that the composite numbers $n$ are rare (under a specific bound). But there are infinitely many of them (over the entire number line). It follows from a theorem in [1] that for any finite set of integers, there are infinitely many Carmichael numbers whose $w(n)$ is not found in the finite set.

___________________________________________________________________

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. Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
3. 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}$