# Another version of the primality test using a theorem of Lucas

In the previous post, we prove a theorem that is attributed to Lucas and give examples on how to use it to prove primality. The task of using this theorem to prove primality is essentially the task of finding a primitive root. So this primality test could be a little tricky to use since there is no simple formula for finding primitive root. In this post, we discuss a variation (but an equivalence) of Lucas’ theorem that does not require using primitive root but still proves primality.

___________________________________________________________________

The theorems

In the previous post, we discuss and prove the following theorem.

Theorem 1 (Lucas)
Let $n$ be a positive integer. Then $n$ is prime if and only if there exists some integer $a$ such that

• $\displaystyle a^{n-1} \equiv 1 \ (\text{mod} \ n)$,
• $\displaystyle a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for all prime factor $r$ of $n-1$.

The value of $a$ in the statement of the theorem is a primitive root modulo $n$. Though the theorem is fairly easy to prove, the theorem is important and has far reaching consequences. The basic idea in this theorem is the foundation of many other deterministic primality tests. So it is a good idea to examine this theorem in great details. One way to do that is to examine variations of it. In this post, we examine the following theorem.

Theorem 2
Let $n$ be a positive integer. Then $n$ is prime if and only if for each prime factor $r$ of $n-1$, there exists some integer $a$ such that

• $\displaystyle a^{n-1} \equiv 1 \ (\text{mod} \ n)$,
• $\displaystyle a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$.

The existential quantifier and the universal quantifier are switched in the statements of the two theorems. In Theorem 1, one value of $a$ works for all prime factors of $n-1$. In Theorem 2, each prime factor of $n-1$ has one value of $a$ that satisfies some conditions. More importantly, the value of $a$ in Theorem 2 cannot be expected to be a primitive root. Computationally speaking Theorem 2 should be a little easier to use. The proof of Theorem of 2 uses the following basic lemma.

Lemma 3
Suppose $g=b_1 \cdot b_2 \cdots b_k$ such that $\text{GCD}(b_i,b_j)=1$ for $i \ne j$. Then if $b_i$ divides $h$ for each $i$, then $g$ divides $h$.

Proof of Lemma 3
Suppose that $b_i$ divides $h$ for each $i$. Assume that $g \le h$. By the division algorithm, we can write $h=g \cdot q+r$ where $q$ and $r$ are integers and $0 \le r. We claim that $r=0$. Once the claim is proved, the lemma will follow.

Suppose that $0. it follows from $h=g \cdot q+r$ that $b_i$ divides $r$ for each $i$. It follows that for some integers $u_i$, the number $r$ can be expressed as follows:

$r=b_1 \cdot u_1=b_2 \cdot u_2=\cdots=b_k \cdot u_k$

Because the numbers $b_i$ are mutually relatively prime, each $b_i$ with $i \ne j$ is a factor of $u_j$. Thus $r=b_1 \cdot b_2 \cdots b_k \cdot w=g \cdot w$ for some integer $w$. We have $0, leading to $0. This is a contradiction since $w$ is an integer.

In the above argument, we make the assumption that $g \le h$. Suppose $h < g$. Using the division algorithm, we have $g=h \cdot q+r$ for some integers $q$ and $r$ with $0 \le r. As before, all the $b_i$ divides $r$. The same argument shows that $r=g \cdot w$ for some positive integer $w$. Now $0 \le g \cdot w , contradicting $h < g$. So the assumption of $g \le h$ is valid. $\blacksquare$

Proof of Theorem 2
The direction $\Longrightarrow$ is clear (see the proof of the same direction in Theorem 1). Now suppose that the number $n-1$ has the following prime factorization

$n-1=p_1^{w_1} \cdot p_2^{w_2} \cdot p_3^{w_3} \cdots p_t^{w_t}$

where each $p_j$ is prime and each $w_j \ge 1$. Suppose that for each prime factor $p_j$, there exists an $a_j$ such that

• $\displaystyle a_j^{n-1} \equiv 1 \ (\text{mod} \ n)$,
• $\displaystyle a_j^{\frac{n-1}{p_j}} \not \equiv 1 \ (\text{mod} \ n)$.
• .

For each $j$, let $k_j$ be the least positive integer such that $\displaystyle a_j^{k_j} \equiv 1 \ (\text{mod} \ n)$. In other words, $k_j$ is the order of $a_j$ modulo $n$. It follows that $k_j$ divides $n-1$. On the other hand, $k_j$ does not divide $\frac{n-1}{p_j}$. If it did, we would have $\displaystyle a_j^{\frac{n-1}{p_j}} \equiv 1 \ (\text{mod} \ n)$.

For each $j$, let $n-1=k_j \cdot m_j$ for some integer $m_j$. Note that $p_j$ cannot divide $m_j$. Otherwise $k_j$ would divide $\frac{n-1}{p_j}$. Since none of the prime factors of $m_j$ can be $p_j$, it follows that $p_j^{w_j}$ must divide $k_j$.

On the other hand, $k_j$ divides $\phi(n)$. So $p_j^{w_j}$ divides $\phi(n)$. By Lemma 3, $n-1$ divides $\phi(n)$, giving $n-1 \le \phi(n)$. It is always that case that $\phi(n) \le n-1$. We have shown that $\phi(n)=n-1$. By Lemma 2 in this previous post, $n$ is prime. $\blacksquare$

___________________________________________________________________

The primality test from the theorems

The above theorems are equivalent. So both theorems give essentially the same primality test. It is just that the implementation based on Theorem 2 is somewhat easier and in some cases much faster. No matter which theorem is used, it is always a good idea to apply the strong probable prime test (the Miller-Rabin test) first, just in case the compositeness can be easily detected.

Of course, the limitation for the primality discussed here is that the factorization of $n-1$ must be known if $n$ is the number being tested. If Lucas’ theorem is not applicable and if probabilistic primality testing is not 100% satisfactory, other primality proving theorems may be explored. See [1].

___________________________________________________________________

Examples

In the previous post, we show how to apply Theorem 1. We now work some examples illustrating the use of Theorem 2.

Example 1
Consider the number $n=$ 38709183810571. The following is the prime factorization of $n-1$.

$n-1=2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \cdot 43 \cdot 53 \cdot 6221671$

The last factor can easily be verified as prime by checking all prime numbers below $\sqrt{6221671}=2495$. Use $a=2$ as a starting point.

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

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

$\displaystyle 2^{\frac{n-1}{3}} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{5}} \equiv 8709312260007 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{7}} \equiv 10281040998090 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{13}} \equiv 19655805387808 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{43}} \equiv 2160876971677 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{53}} \equiv 9896596763553 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{6221671}} \equiv 787783558192 \not \equiv 1 \ (\text{mod} \ n)$

Note that the number $a=2$ works for all prime factors of $n-1$ except for 3. Now use $a=3$.

$\displaystyle 3^{\frac{n-1}{3}} \equiv 38709177588900 \not \equiv 1 \ (\text{mod} \ n)$

In conclusion, for all prime factors of $n-1$ except 3, the value $a=2$ satisfies the conditions in Theorem 2. For the prime factor 3 of $n-1$, use $a=3$. By Theorem 2, the number $n=$ 38709183810571 is proved to be prime.

Example 2
Use Theorem 2 to perform primality testing on the following number

$n=$ 3825123056546413183.

This is Example 2 in this previous post. The factorization of $n-1$ is

$2 \cdot 3 \cdot 11 \cdot 17 \cdot 211 \cdot 16157348744821$.

The last factor $m=$ 16157348744821 is a prime number (see the previous post). We start with $a=2$.

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

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

$\displaystyle 2^{\frac{n-1}{3}} \equiv 289450338018998060 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{11}} \equiv 1901835040937234167 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{17}} \equiv 914194133070825051 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{211}} \equiv 762829414677449095 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{16157348744821}} \equiv 3383930647831278184 \not \equiv 1 \ (\text{mod} \ n)$

With $a=2$, the above calculation works for all prime factors of $n-1$, except 2. Now try $a=3$.

$\displaystyle 3^{\frac{n-1}{2}} \equiv -1 \ (\text{mod} \ n)$

By Theorem 2, the number $n=$ 3825123056546413183 is proved prime.

___________________________________________________________________

Exercises

Prove the compositeness or primality of each of the following numbers. In proving primality, use Lucas’ theorem according to Theorem 2.

204482919124364689
3825123056546413093
3825123056546413133
3825123056546413211
3825123056546413213

___________________________________________________________________

Reference

1. Brillhart J., Lehmer D. H., Selfridge J.L., New primality criteria and factorizations of $2^m \pm 1$, Math. Comp., 29, no. 130, 620-647, 1975.
2. Lehmer D. H., Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc., 33, 327-340 1927.

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

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

# Large examples of strong pseudoprimes to several bases

A strong pseudoprime to base $a$ is a composite number that passes the strong probable prime test (i.e. the Miller-Rabin test) in the base $a$. There are indications that strong pseudoprimes are rare. According to [6], there are only 4842 numbers below $25 \cdot 10^9$ that are strong pseudoprimes to base 2. Strong pseudoprimes to several bases are even rarer. According to [6], there are only 13 numbers below $25 \cdot 10^9$ that are strong pseudoprimes to bases 2, 3 and 5. The paper [4] tabulates the numbers below $10^{12}$ that are strong pseudoprimes to bases 2, 3 and 5. That listing contains only 101 numbers. These examples show that strong pseudoprimes to several bases may be rare but they do exist. In this post we discuss two rather striking examples of large numbers that are strong pseudoprimes to the first 11 prime bases for the first one and to the first 46 prime bases for the second one. One important lesson that can be drawn from these examples is that the implementation of the strong probable prime test must be randomized.

___________________________________________________________________

The strong probable prime test

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. Then calculate the following sequence of $k+1$ numbers:

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

where $a$ is some integer relatively prime to $n$. The first term $a^Q$ can be efficiently calculated using the fast powering algorithm. Each subsequent term is the square of the preceding term. Each term is reduced modulo $n$.

If $a^Q \equiv 1 \ (\text{mod} \ n)$ (i.e. the first term in sequence (1) is a 1) or $a^{2^j \cdot Q} \equiv -1 \ (\text{mod} \ n)$ for some $j=0,1,2,\cdots,k-1$ (i.e. the term preceding the first 1 in the sequence is a -1), then $n$ is said to be a strong probable prime to the base $a$. A strong probable prime to base $a$ could be a prime or could be composite. If the latter, it is said to be a strong pseudoprime to base $a$. In fact, most strong probable primes to one base are prime.

The strong probable prime test consists of checking whether $n$ is a strong probable prime to several bases. If $n$ is not a strong probable prime to one of the bases, then $n$ is composite for sure. If $n$ is a strong probable prime to all of the bases being used, then $n$ is likely a prime number in that the probability that it is composite is at most $4^{-u}$ if $u$ is the number of bases.

The last probability of $4^{-u}$ is what makes the 337-digit number $N$ defined below striking. Here we have a number that is a strong probable prime to 46 bases. What could go wrong in declaring it a prime number? The problem is that using a pre-determined set of bases is not a randomized implementation of the strong probable prime test.

___________________________________________________________________

Examples

The following is a 46-digit found in [3] that is a strong pseudoprime to the first 11 prime bases (the prime numbers from 2 to 31).

$M=$
1195068768795265792518361315725116351898245581

The following is a 337-digit number found in [3] that is a strong pseudoprime to all 46 prime bases up to 200 (the prime numbers from 2 to 199).

$N=$
80383745745363949125707961434194210813883768828755
81458374889175222974273765333652186502336163960045
45791504202360320876656996676098728404396540823292
87387918508691668573282677617710293896977394701670
82304286871099974399765441448453411558724506334092
79022275296229414984230688168540432645753401832978
6111298960644845216191652872597534901

The following sets up the calculation for the Miller-Rabin test (strong probable prime test).

$M-1=2^2 \cdot Q$

$N-1=2^2 \cdot R$

where $Q$ and $R$ are odd and

$Q=$
298767192198816448129590328931279087974561395

$R=$
20095936436340987281426990358548552703470942207188
95364593722293805743568441333413046625584040990011
36447876050590080219164249169024682101099135205823
21846979627172917143320669404427573474244348675417
70576071717774993599941360362113352889681126583523
19755568824057353746057672042135108161438350458244
6527824740161211304047913218149383725

___________________________________________________________________

Random bases

Though the second number $N$ is very striking, the author of [3] has an even larger example in [2], a 397-digit Carmichael number that is a strong pseudoprime to all the 62 prime bases under 300! One lesson from these examples is that the implementation of the strong probable prime test should be randomized, or at least should include some randomly chosen bases in the testing. Any algorithm that implements the strong probable prime test in any “fixed” way (say, only checking the prime bases up to a certain limit) may incorrectly identify these rare numbers as prime.

Let’s apply the strong probable prime test on the above numbers $N$ and $M$ using some random bases. Consider the following randomly chosen bases $b$ and $c$ where $1 and $1.

$b=$
932423153687800383671087185189848318498417236

$c=$
23876349986768815408041169070899917334655923628776
58344592618224528502905948639172375368742187714892
08287654410018942444630244906406410549094447554821
42803219639200974486541191341820595453041950723891
75748815383568979859763861820607576949539863746244
98291058421101888215044176056586791235119485393994
789287924346696785645273545040760136

___________________________________________________________________

The calculation using random bases

Here’s the calculation for the 46-digit number $M$.

$b^Q \equiv t_1 \ (\text{mod} \ M)$

$b^{2 \cdot Q} \equiv t_2 \ (\text{mod} \ M)$

$b^{M-1}=b^{4 \cdot Q} \equiv t_3 \ (\text{mod} \ M)$

where $t_1$, $t_2$ and $t_3$ are:

$t_1=$
1042866890841899880275968177787239559549445173

$t_2=$
826876320842405260107866407865475914456579581

$t_3=$
1195068768795265792518263537659322626328455738

Note that the last number $t_3$ is not a 1. So the number $M$ is not a strong probable prime to base $b$. This means that it is composite.

Here’s the calculation for the 337-digit number $N$.

$c^R \equiv g_1 \ (\text{mod} \ N)$

$c^{2 \cdot R} \equiv g_2 \ (\text{mod} \ N)$

$c^{N-1}=c^{4 \cdot R} \equiv g_3 \ (\text{mod} \ N)$

where $g_1$, $g_2$ and $g_3$ are:

$g_1=$
43050290968654965761881145696359381339174664947842
93659429396009893693594328847691223585119425166890
43134041173054778367051375333950357876719375530986
40705386242996844394887879855798166233504226845778
76290707027478869178569806270616567220414388766208
75314254126730991658967210391794715621886266557484
525788655243561737981785859480518172

$g_2=$
69330060289060873891683879069908453474713549543545
79381982871766126161928753307995063953670075390874
26152164526384520359363221849834543643026694082818
11219470237408138833421506246436132564652734265549
18153992550152009526926092009346342470917684117296
93655167027805943247124949639747970357553704408257
9853042920364675222045446207932076084

$g_3=$
80383745745363949125707961434194210813883768828755
81458374889175222974273765333652186502336163960045
45791504202360320876656996676098728404396540823292
87387918508691668493091034289810372813316104284761
45244183107779151749589951324358651494383103941607
35777636976785468267798055151468799251924355070195
1772723904683953622590747688533861698

Interestingly, the last number $g_3$ agrees with the modulus $N$ from the first digit (the largest) to digit 167. It is clear that $g_3$ is clearly not a 1. So the 337-digit number $N$ is not a strong probable prime to base $c$, meaning it is composite. Even though the number $M$ is a strong pseudoprime to all of the first 46 prime bases, it is easy to tell that it is composite by using just one random base. This calculation demonstrates that it is not likely to make the mistake of identifying large pseudoprimes as prime if randomized bases are used in the strong probable prime test.

___________________________________________________________________

Some verification

We also verify that the 46-digit $M$ is a strong pseudoprime to the first 11 prime bases.

$\left[\begin{array}{rrrrrrr} a & \text{ } & a^Q \ (\text{mod} \ M) & \text{ } & a^{2Q} \ (\text{mod} \ M) & \text{ } & a^{4Q} \ (\text{mod} \ M) \\ \text{ } & \text{ } & \text{ } \\ 2 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 3 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 5 & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \\ 7 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 11 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 13 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 17 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 19 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 23 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 29 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \\ 31 & \text{ } & * & \text{ } & -1 & \text{ } & 1 \end{array}\right]$

The asterisks in the above table mean that those cells have numbers that are $\not \equiv \pm 1$ modulo $M$. Clearly the table shows that the number $M$ passes the strong probable prime test for these 11 bases. We also verify that $M$ is not a strong probable prime to base 37, the next prime base.

$37^Q \equiv w_1 \ (\text{mod} \ M)$

$37^{2 \cdot Q} \equiv w_2 \ (\text{mod} \ M)$

$37^{M-1}=b^{4 \cdot Q} \equiv w_3 \ (\text{mod} \ M)$

where

$w_1=$
977597583337476418144488003654858986215112009

$w_2=$
368192447952860532410592685925434163011455842

$w_3=$
1195068768795265792518263537659322626328455738

Note that the last number $w_3$ agrees with the modulus $M$ for the first 22 digits and they differ in the subsequent digits. It is clear that $w_3$ is not 1. So the strong pseudoprimality of $M$ stops at the base 37.

We do not verify the number $N$ for all the 46 prime bases. We only show partial verification. The following calculation shows the pseudoprimality of $N$ to bases 197 and 199, and that the strong pseudoprimality of $N$ fails at 211, the next prime base.

$197^R \equiv * \ (\text{mod} \ N)$

$197^{2 \cdot R} \equiv -1 \ (\text{mod} \ N)$

$197^{N-1}=197^{4 \cdot R} \equiv 1 \ (\text{mod} \ N)$

__________________

$199^R \equiv * \ (\text{mod} \ N)$

$199^{2 \cdot R} \equiv -1 \ (\text{mod} \ N)$

$199^{N-1}=199^{4 \cdot R} \equiv 1 \ (\text{mod} \ N)$

__________________

$211^R \equiv v_1 \ (\text{mod} \ N)$

$211^{2 \cdot R} \equiv v_2 \ (\text{mod} \ N)$

$211^{N-1}=211^{4 \cdot R} \equiv 1 \ (\text{mod} \ N)$

where

$v_1=$
48799236892584399744277334997653638759429800759183
35229821626086043683022014304157526246067279138485
99367014952239377476103536546259094903793421522217
99291447356172114871135567262925519534270746139465
22832800077663455346130103616087329184090071367607
57478119260722231575606816699461642864577323331271
2974554583992816678859279700007174348

$v_2=$
80191643327899921083661290416909370601037633208226
50175490124094760064341402392485432446383194439467
16432633017071633393829046762783433857505596089159
3600905184063673203

Note that $v_2$ is clearly not congruent to -1. Thus the number $N$ is not a strong pseudoprime to base 211 (though it is a pseudoprime to base 211). Clearly, the above calculation indicates that the number $N$ is a strong pseudoprime to bases 197 and 199.

___________________________________________________________________

Remark

Because strong pseudoprimes are rare (especially those that are strong pseudoprimes to several bases), they can be used as primality tests. One idea is to use the least pseudoprimes to the first $n$ prime bases [5]. This method is discussed in this previous post.

Another idea is to use the listing of strong pseudoprimes to several bases that are below a bound. Any number below the bound that is strong probable primes to these bases and that is not on the list must be a prime. For example, Table 1 of [4] lists 101 strong pseudoprimes to bases 2, 3 and 5 that are below $10^{12}$. This test is fast and easy to use; it requires only three modular exponentiations to determine the primality of numbers less than $10^{12}$.

The numbers $M$ and $N$ are not Carmichael numbers since $b^{M-1} \not \equiv 1 \ (\text{mod} \ M)$ and $c^{N-1} \not \equiv 1 \ (\text{mod} \ N)$, making the random numbers $b$ and $c$ Fermat witnesses for these two numbers respectively. Another way to see that they are not Carmichael is that each of the two number $M$ and $N$ is also a product of two distinct primes according to [3].

An even more striking result than the examples of $M$ and $N$ is that it follows from a theorem in [1] that for any finite set of bases, there exist infinitely many Carmichael numbers which are strong pseudoprimes to all the bases in the given finite set. This is discussed in the next post.

___________________________________________________________________

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. Arnault F., Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Computation, 20, 151-161, 1995.
3. Arnault F., Rabin-Miller primality test: composite numbers that pass it, Math. Comp., Volume 64, No. 209, 355-361, 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, No. 151, 1003-1026, 1980.

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