Pepin’s Primality Test

A Fermat number is of the form $F_n=2^{2^{n}}+1$ where $n$ is a nonnegative integer. A Fermat prime is a Fermat number that is a prime number. The first five Fermat numbers $F_0$ to $F_4$ are known to be prime. Pierre de Fermat (1601-1665) conjectured that all Fermat numbers are prime. In 1732, Euler discovered a counterexample by showing that $F_5$ is composite with $F_5=641 \times 6700417$. The challenge for working with Fermat numbers is that the numbers grow very rapidly. However, Fermat numbers have many interesting properties. See here for a more detailed look. In this post, we discuss Pepin’s test, which is a primality test solely for Fermat numbers, as well as a sequence of integers that are associated with Fermat numbers. Out of this sequence of integers comes the notion of elite prime numbers.

The following are two versions of the Pepin’s test. Theorem 1 is proved in this previous post.

Theorem 1 (Pepin’s Test)
For any $n \ge 1$, the Fermat number $F_n$ is a prime number if and only if $3^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n)$.

Theorem 2 (Pepin’s Test)
For any $n \ge 2$, the Fermat number $F_n$ is a prime number if and only if $5^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n)$.

To determine whether a Fermat number $F_n$ is prime, simply raise 3 (or 5) to the exponent of $(F_n-1)/2$ modulo $F_n$. If the result is congruent to -1, then $F_n$ is prime. Otherwise it is composite. The exponentiation can be performed using the fast powering algorithm (also called square-and-multiply). The idea is to use the binary expansion of the exponent to convert the exponentiation into a series of squarings and multiplications. For Pepin’s test, the exponent is a power of 2. Thus the binary expansion is a 1 followed by a number of zeros. As a result, in programming the “square-and-multiply”, we only need to program the squarings.

The above two versions of Pepin’s test use 3 and 5 as bases. An interesting and natural question arises. What are all the numbers that can serve as bases for the Pepin’s test? In fact, there are many other bases. What would be the property that unites all the possible bases? The sequence A129802 in OEIS describes all possible bases for use in Pepin’s test. In this post, we give a formulation of Pepin’s test that takes into account all the possible bases in this sequence. We also discuss the prime numbers in the sequence, which are also captured in the sequence A102742 (these are called elite prime numbers).

___________________________________________________________________

The Periodic Nature of Fermat Numbers

Let $a$ be any positive integer with $a \ge 3$. Consider all Fermat numbers $F_n$ reduced modulo $a$, i.e. $F_n \ (\text{mod} \ a)$. We call these values the Fermat remainders modulo $a$. Since there are only $a$ many such values, i.e. $0, 1, 2, \cdots, a-1$ and since Fermat numbers can be derived by the recursive formula

$F_{n+1}=(F_n-1)^2+1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (0)$

the Fermat remainders are periodic. Let’s look at an example.

Let $a=41$. The following shows the first several Fermat remainders modulo 41. Each value is computed from the previous value via the recursive relation $(0)$, which is then reduced modulo 41.

$F_0 \equiv 3 \ (\text{mod} \ 41)$

$F_1 \equiv 5 \ (\text{mod} \ 41)$

$F_2 \equiv 17 \ (\text{mod} \ 41)$

$F_3 \equiv 257 \equiv 11 \ (\text{mod} \ 41)$

$F_4 \equiv 101 \equiv 19 \ (\text{mod} \ 41)$

$F_5 \equiv 325 \equiv 38 \ (\text{mod} \ 41)$

$F_6 \equiv 1370 \equiv 17 \ (\text{mod} \ 41)$

It is clear the Fermat remainders 17, 11, 19, 38 repeat themselves as $n$ increases. For Fermat remainders modulo 41, the periodicity starts at $F_2$ and the length of the period is 4 (we call this the Fermat period).

Let’s describe idea behind the example more generally. Because any Fermat remainder must be an element of $\left\{0,1,\cdots,a-1 \right\}$, there exist at least two Fermat numbers sharing the same remainder, say $F_h$ and $F_k$ with $h. Assume that $h$ and $k$ are the smallest possible choices. In the modulo 41 example, $h$ would be 2 and $k$ would be 6. As a result, $F_h$ is the starting point of the period and $L=k-h$ is the length of the Fermat period.

Based on the discussion in the above paragraph, for any positive integer $a \ge 3$, the Fermat remainders modulo $a$ are periodic with the repeating remainders starting at some Fermat number $F_h$. The length of the Fermat period is the smallest positive integer $L$ satisfying the congruence $F_{h+j} \equiv F_{h+j+m \cdot L} \ (\text{mod} \ a)$ for all $j=0,1,\cdots,L-1$ and for all positive integer $m$.

The symbol $(\frac{p}{q})$ is a Legendre symbol if the bottom number is a prime number, in which case the value of the symbol is 1 or -1. If the bottom number is a composite number, then it is a Jacobi symbol with possible values 0, 1 or -1.

We now wish to evaluate the symbol $(\frac{a}{F_n})$ where the bottom part is a Fermat number and the top part is a possible base for Pepin’s test. Consider the following derivation.

$\displaystyle \biggl(\frac{a}{F_n}\biggr)=\biggl(\frac{F_n}{a}\biggr)=\biggl(\frac{r}{a}\biggr) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The first Jacobi symbol can be flipped without changing sign because $F_n \equiv 1 \ (\text{mod} \ 4)$ for all $n \ge 1$. This is due to the law of quadratic reciprocity of Jacobi symbol (see bullet # 6 in Theorem 6 here). The number $r$ in the top part of the third Jacobi symbol represents all the possible Fermat remainders modulo $a$. For example, if $a=41$, $r$ would be 17, 11, 19 or 38. The above relation in Jacobi symbol is how we tie Fermat remainders with the Pepin’s test.

___________________________________________________________________

The Sequences

The following theorem gives the linkage between Fermat remainders and the Pepin’s test.

Theorem 3
Let $a$ be a positive integer where $a \ge 3$. The following conditions are equivalent.

1. The Jacobi symbol $(\frac{r}{a})=-1$ for all Fermat remainders $r$ modulo $a$.
2. There is a positive integer $h$ such that the Jacobi symbol $(\frac{a}{F_n})=-1$ for all $n \ge h$.

Proof of Theorem 3
Note that if condition 1 is not true, then there is one Fermat remainder $r$ such that the Jacobi symbol $(\frac{r}{a})=1$. Since the Fermat remainders are periodic, via relation $(1)$ above there are infinitely many $F_n$ with $(\frac{a}{F_n})=1$. Thus condition 2 is not true. In other words, $2 \rightarrow 1$ holds. On the other hand, if condition 2 is not true, then condition 1 is not true. $\square$

Any positive integer $a$ belongs to the sequence A129802 if and only of one of the conditions in Theorem 1 holds. Note that 2 does not belong to the sequence. To see this, note that $F_{n} \equiv 1 \ (\text{mod} \ 2)$ for all $n$. So there is only one Fermat remainder modulo 2, namely 1. Since the Legendre symbol $(\frac{1}{2})=1$, condition 1 in Theorem 1 is not true. Thus all possible members of the sequence A129802 must be 3 or higher. The numbers 3 and 5 both belong to the sequence. Both numbers have only one Fermat remainder, namely 2. Note that $F_{n} \equiv 2 \ (\text{mod} \ 3)$ for all $n \ge 1$ and $F_{n} \equiv 2 \ (\text{mod} \ 5)$ for all $n \ge 2$. Also note that the Legendre symbols $(\frac{2}{3})=-1$ and $(\frac{2}{5})=-1$.

What if we limit the scope of Theorem 3 to just the prime numbers? The following is the translation of Theorem 3 where $p$ is a prime number (using $p$ to replace $a$).

Theorem 4a
Let $p$ be a prime number. The following conditions are equivalent.

1. The Legendre symbol $(\frac{r}{p})=-1$ for all Fermat remainders $r$ modulo $p$.
2. There is a positive integer $h$ such that the Legendre symbol $(\frac{F_n}{p})=-1$ for all $n \ge h$.

Condition 2 of Theorem 4a should start with the Jacobi symbol $(\frac{a}{F_n})$. Since it can be flipped without changing sign, it become the Legendre symbol $(\frac{F_n}{a})$. Next, the following theorem is obtained by rewriting Theorem 4a using the meaning of the Legendre symbol.

Theorem 4b
Let $p$ be a prime number. The following conditions are equivalent.

1. For each Fermat remainders $r$ modulo $p$, $r$ is a quadratic nonresidue modulo $p$
2. For each Fermat remainders $r$ modulo $p$, the congruence $r^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ holds.
3. There is a positive integer $h$ such that the Fermat number $F_n$ is a quadratic nonresidue modulo $p$ for all $n \ge h$.

Note that condition 2 in Theorem 4b is due to Euler’s criterion.

Any prime number $p$ that satisfies any one of the conditions in Theorem 4b is said to be an elite prime number. Thus an elite prime can be used as a base for the Pepin’s test and is a member of the sequence A129802. In fact, another sequence A102742 is to capture all the elite prime numbers.

Note that 3 and 5 are elite primes as is the prime number 41. The Fermat remainders modulo 41 are 17, 11, 19 and 38 (as shown above). All of the 4 Fermat remainders are quadratic nonresidue modulo 41. The Legendre symbols have value -1 as shown below:

$\displaystyle \biggl(\frac{17}{41}\biggr)=\biggl(\frac{11}{41}\biggr)=\biggl(\frac{19}{41}\biggr)=\biggl(\frac{38}{41}\biggr)=-1$

Before further discussing elite primes, let’s have a more general statement of Pepin’s test.

___________________________________________________________________

Pepin’s Test – General Version

Theorem 5 (Pepin’s Test)
Let $a \ge 3$ be an integer such that there exists a positive integer $h$ such that the Jacobi symbol $(\frac{a}{F_n})=-1$ for all $n \ge h$. In other words, $a$ is a member of the sequence A129802. Then for any $n \ge h$, the Fermat number $F_n$ is a prime number if and only if $a^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n)$.

Proof of Theorem 5
Let $a \ge 3$ be a number that satisfies the requirement in Theorem 5, i.e. it is a member of the sequence A129802. Let $n \ge h$. Suppose that $F_n=2^{2^n}+1$ is prime. Then the symbol $(\frac{a}{F_n})$ is a Legendre symbol. By the Euler’s criterion, we have $a^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n)$.

Suppose that the congruence $a^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n)$ holds. Then by Lucas primality test, $F_n$ is prime. For the details, see the proof of Theorem 7 in this previous post. $\square$

Theorem 5 is a version of Pepin’s test that takes into account of all the possibilities for a base. Any number in the sequence A129802 will work. This version is more interesting from a mathematical standpoint. In practice, to use Pepin’s test, we must first settle on a base. Pick a number from list of A129802 or find some number $a$ that satisfies one condition in Theorem 3. It is also important to determine the least number $h$ for the condition in Theorem 3. The $h$ is the lower bound for the $F_n$ that can be tested by Pepin’s test. Of course, it is handy to use 3 or 5 as a base. Thus the versions such as Theorem 1 and Theorem 2 above are useful in practice. Mathematically Theorem 5 is more interesting. It brings out the concept of the integer sequence A129802 and the notion of elite prime.

___________________________________________________________________

More on the Sequences

There is one natural question about the A129802 (possible bases for Pepin’s test) and the sequence A102742 (possible prime bases for Pepin’s test, the elite primes). Does each sequence contain infinitely many numbers? The answer is not known for the second sequence (the elite primes). It is not known whether there are infinitely many elite primes. However, we can show that the first sequence infinitely many members.

Theorem 6

• If $a$ is a member of the sequence A129802, then the number $2 \times a$ is also a member of the sequence.
• If $a$ is a member of the sequence A129802, then for any integer $k \ge 0$, the number $2^k \times a$ is also a member of the sequence.

Proof of Theorem 6
We prove the first bullet point. The second follows from the first. Since $a$ is in the sequence A129802 (i.e. it satisfies Theorem 3), there is a least $h$ such that $(\frac{a}{F_n})=-1$ for all $n \ge h$. The following derivation shows that $(\frac{2a}{F_n})=-1$ for all $n \ge h$.

$\displaystyle \biggl(\frac{2a}{F_n}\biggr)=\biggl(\frac{2}{F_n}\biggr) \times \biggl(\frac{a}{F_n}\biggr)=\biggl(\frac{F_n}{2}\biggr) \times \biggl(\frac{F_n}{a}\biggr)=\biggl(\frac{1}{2}\biggr) \times -1=-1$

In the above derivation, a property of Jacobi symbol is used along with the fact that 1 is a quadratic residue modulo 2 and the fact that $(\frac{a}{F_n})=(\frac{F_n}{a})=-1$. $\square$

Since 3 is a base for Pepin’s test, 3, 6, 12, 24, 48, 96, … are also bases for Pepin’s test.

___________________________________________________________________

Elite Primes

From the perspective of Fermat numbers, elite prime numbers are simply prime numbers that can serve as bases for Pepin’s primality test for Fermat numbers. Of course this is not a good working definition. Theorem 5 tells us that any prime number that can work as a base for Pepin’s test satisfies the conditions in Theorem 4b (or 4a). Thus we can define elite primes by Theorem 4b. Any odd positive integer $p$ is an elite prime if it satisfies anyone of the conditions in Theorem 4b. We introduce the notion of elite prime by way of Pepin’s test of primality of Fermat numbers. Of course, it is possible to define the notion by using only the conditions in Theorem 4b.

As of the writing of this post, there are 29 known elite primes. The smallest are 3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041. The largest is 3,580,135,407,617, about 3.58 trillion. According to the prime number theorem, there are approximately 124 billion prime numbers in this range. So elite primes are very sparse in the number line. No one know whether there are infinitely many elite primes.

How does one test whether a prime number is an elite prime? One way is to use Theorem 4b. Identify the Fermat remainders modulo the prime $p$. Compute the congruence $r^{\frac{p-1}{2}} \ (\text{mod} \ p)$ for each remainder $r$. If $r^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ for all $r$, then $p$ is an elite prime. it turns out that if $p$ is indeed elite, the calculation to verify is quite light. If $p$ is not elite, there usually is a Fermat remainder early on that disproves the eliteness. We close with two examples.

Example 1
Verify that the largest known elite prime 3,580,135,407,617 is indeed elite.

Let $p$ = 3,580,135,407,617. Then $p-1=2^{16} \times$ 54,628,531. This means that the period will start at or before $F_{16}$. The following shows the Fermat remainders.

$F_0 \equiv$ 3
$F_1 \equiv$ 5
$F_2 \equiv$ 17
$F_3 \equiv$ 257
$F_4 \equiv$ 65537
$F_5 \equiv$ 4294967297
$F_6 \equiv$ 3302442361075
$F_7 \equiv$ 3290048612191
$F_8 \equiv$ 2705228890692
$F_9 \equiv$ 3257180532505
$F_{10} \equiv$ 517702690191
$F_{11} \equiv$ 690766084782
$F_{12} \equiv$ 1306969066177
$F_{13} \equiv$ 2982034914426
$F_{14} \equiv$ 3080321286431
$F_{15} \equiv$ 123155921421
$F_{16} \equiv$ 3185964351132
$F_{17} \equiv$ 2462332130355
$F_{18} \equiv$ 3164234988981
$F_{19} \equiv$ 395355620647
$F_{20} \equiv$ 2009257348278
$F_{21} \equiv$ 2441138263337
$F_{22} \equiv$ 499814121188
$F_{23} \equiv$ 123155921421

The Fermat period starts at $F_{15}$. The length of the period is 8 (the remainders are in bold). Let $r_j$ denote the remainder of $F_j$. Now raise each remainder to the power of $\frac{p-1}{2}$ modulo $p$. The following shows the results.

$(r_{15})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

$(r_{16})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

$(r_{17})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

$(r_{18})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

$(r_{19})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

$(r_{20})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

$(r_{21})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

$(r_{22})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)$

The calculation shows that each Fermat remainder is a quadratic nonresidue modulo 3,580,135,407,617. Thus it is an elite prime. $\square$.

Example 2
The next prime number beyond the elite prime in Example 1 is $p$ = 3,580,135,407,647. Show that it is not elite.

Note that $p-1$ = 2 x 1,790,067,703,823. Because the exponent in the power of 2 is 1, the period would begin at $F_1$ or $F_0$. For some reason, the length of the Fermat period for a non-elite prime can be very long. The following shows the first 13 or 14 remainders.

$F_0 \equiv$ 3
$F_1 \equiv$ 5
$F_2 \equiv$ 17
$F_3 \equiv$ 257
$F_4 \equiv$ 65537
$F_5 \equiv$ 4294967297
$F_6 \equiv$ 3302287785295
$F_7 \equiv$ 2157778759259
$F_8 \equiv$ 2823039261272
$F_9 \equiv$ 1745925786363
$F_{10} \equiv$ 1237739799756
$F_{11} \equiv$ 2960576514326
$F_{12} \equiv$ 258269474223
$F_{13} \equiv$ 2361028595996

Fortunately one of the early remainders disproves the eliteness. The following shows that calculation.

$(r_{0})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$
$(r_{1})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{2})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{3})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$
$(r_{4})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{5})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{6})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$
$(r_{7})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{8})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{9})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{10})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{11})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)$
$(r_{12})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$
$(r_{13})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$

Even though the Fermat period may be very long in this case, there are several Fermat remainders early that show $r^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$. This shows that the prime in this example cannot be elite. $\square$

The notion of elite primes is an interesting one. Even though the initial motivation is Pein’s test – a primality test for Fermat numbers, the notion of elite prime is interesting in its own right. There had been a lot of research done, both computationally and mathematically. See the references listed in the two OEIS sequences A129802 and A102742.

___________________________________________________________________
$\copyright \ \ 2016 \ \text{Dan Ma}$ Let

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

A primality proving algorithm using a theorem of Lucas

In this post we discuss a theorem that can be used as a primality test that actually proves primality rather than just giving strong evidence for primality. The theorem is originally due to Lucas in 1891. The version we discuss here is proved by Lehmer [1]. The primality test using the theorem is a limited one since the test requires that $n-1$ must be completely factored if $n$ is the number being tested. Though a limited test, this is a useful test in situations where $n-1$ has small prime factors or the factorization of $n-1$ is known in advance (e.g. factorial primes and primorial primes).

___________________________________________________________________

The 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 function $\phi$ is Euler’s phi function. If $n$ is a prime number, $\phi(n)=n-1$. The following lemma shows that the converse is true. The lemma is used in proving Theorem 1.

Lemma 2
If $\phi(n)=n-1$, then $n$ is prime.

Proof of Lemma 2
By definition $\phi(n)$ is the number of integers $t$ where $1 such that $\text{GCD}(t,n)=1$, i.e., $t$ and $n$ are relatively prime. First of all, $\phi(n) \le n-1$. Suppose $n$ is composite. Then there is some $t$ where $1 such that $t$ is a divisor of $n$. Clearly $\text{GCD}(t,n)>1$. It follows that $\phi(n). Therefore if If $\phi(n)=n-1$, then $n$ must be prime. $\blacksquare$

Proof of Theorem 1
It is well known that for any prime number $n$, there exists a primitive root modulo $n$ (see here). A primitive root modulo $n$ is a number $a$ such that $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$ but $a^{j} \not \equiv 1 \ (\text{mod} \ n)$ for all $1. In other words, $\phi(n)$ is the least exponent such that $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$. Let $n$ be a prime number. Then $\phi(n)=n-1$. By the point that is just stated, there exists an $a$ that is a primitive root modulo $n$. This primitive root $a$ would satisfy $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ and $a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for any prime divisor $r$ of $n-1$.

Now suppose that there exists an $a$ such that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ and $a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for any prime divisor $r$ of $n-1$. Let $k$ be the least positive integer such that $a^{k} \equiv 1 \ (\text{mod} \ n)$. The number $k$ is said to be the order of $a$ modulo $n$.

We claim that $k=n-1$. From the assumption that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$, we have $k \lvert (n-1)$. Thus $k \le n-1$. Suppose that $k. Then $\frac{n-1}{k}$ is an integer that is greater than 1. Let $r$ be a prime factor of $\frac{n-1}{k}$. Set $\frac{n-1}{k}=r \cdot t$ for some integer $t$. Then $a^{\frac{n-1}{r}} \equiv a^{kt} \equiv (a^k)^t \equiv 1 \ (\text{mod} \ n)$, contradicting the assumption stated above. Thus $k=n-1$.

On the other hand, $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$ always holds (see here). Since $k$ is least, we have $k=n-1 \le \phi(n)$. It is always the case that $\phi(n) \le n-1$. Thus we have established that $\phi(n)=n-1$. By Lemma 2, $n$ is prime. $\blacksquare$

Remark
The above proof shows that $n$ is prime from the existence of $a$ such that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ and $a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for any prime divisor $r$ of $n-1$. The proof also shows that $\phi(n)$ is the least number such that $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$. That is, the number $a$ is a primitive root modulo $n$. Whenever $n$ is proved prime by finding such an $a$, keep in mind that the task of primality proving using this theorem is essentially the task of finding a primitive root.

___________________________________________________________________

The primality test from the theorem

Theorem 1 can be fashioned into a primality test, or rather a primality proving algorithm. The key requirement to proving $n$ is prime is that $n-1$ must be completely factored. Because of this obstacle, the primality test is a limited one. The following are some of the cases for which Lucas’s theorem is suitable as a proof for the primality of $n$.

• All prime factors of $n-1$ are small.
• For each prime factor of $n-1$, either it is small or its primality can be established using Lucas’s theorem.

The second case points to the fact that sometimes Lucas’ theorem can be used recursively to establish the primality of a number. Specifically, in factoring $n-1$, we may come across a factor that is a probable prime. We then can use Lucas’ theorem to prove its primality. In doing so, we may come across another number that is a probable prime. We can then use Lucas’ theorem again and prove its primality and so on.

As mentioned at the end of the previous section, the task of primality proving here is essentially the task of finding a primitive root. There is no easy formula for finding primitive roots. One can always start with $a=2$ and work the way up to a value of $a$ that works. But this may be a lengthy process. A faster option is to use randomly chosen values of $a$.

To use Theorem 1 to prove that $n$ is prime, it is a matter of finding a value of $a$ with $1 that satisfies the two conditions in the theorem. If such an $a$ is not found after a reason number of iterations, then $n$ is probably composite. In this case, it makes sense to subject $n$ to a probabilistic primality test such as the Miller-Rabin test to check for compositeness.

In light of the comment made in the preceding paragraph, before using Theorem 1, we should apply a probabilistic primality test on the number being tested. If the number is shown to be composite by the Miller-Rabin test, then there is no need to use Theorem 1. If the number is a strong probable prime to base 2 for example, then we can proceed to use Theorem 1. Even when Theorem 1 is applicable, there may still be a need to switch back to a probabilistic primality test if a suitable value of $a$ cannot be found in a reasonable number of iterations. Additional remark is given at the end of Example 1.

___________________________________________________________________

Examples

The examples demonstrated here are small enough to be realistically proved as prime by factoring (by computer). However, they are large enough to be excellent demonstrations of the method using the theorem of Lucas.

Example 1

Consider the number $n=$ 3825123056546413057. As a preliminary check, we find that it is a strong probable prime to base 2. The following is the prime factorization of $n-1$.

$n-1=2^9 \cdot 3 \cdot 53 \cdot 647 \cdot 2689 \cdot 2927 \cdot 9227$

Choose a random number $a$ in the interval $1. Then calculate the following 8 congruences.

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

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

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

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

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

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

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

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

If the first one is a 1 and the other 7 congruences are not 1, then we have a proof that $n=$ 3825123056546413057 is prime. Using the random number $a=$ 986534828637101811, we have the following results.

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

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

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

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

$\displaystyle a^{\frac{n-1}{647}} \equiv 1877702458518081231 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2689}} \equiv 2711620409082022280 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2927}} \equiv 2162838710620876676 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{9227}} \equiv 178583766553568086 \not \equiv 1 \ (\text{mod} \ n)$

The first congruence is a 1 and the remaining 7 congruences are not 1. Thus by Lucas’ theorem, the number $n=$ 3825123056546413057 is prime.

Remarks
Upon choosing a value of $a$ (random or otherwise), if the first congruence $\displaystyle a^{n-1} \ (\text{mod} \ n)$ is not a 1, then $n$ is composite by Fermat’s little theorem, and we are done. Suppose the first congruence is a 1. If the second congruence $\displaystyle a^{\frac{n-1}{2}} \ (\text{mod} \ n)$ is not $\pm 1$, then $n$ is composite. This is because if $n$ is prime, then the square root of 1 modulo $n$ must be $\pm 1$. Since Lucas’ theorem requires that $\displaystyle a^{\frac{n-1}{2}} \not \equiv 1 \ (\text{mod} \ n)$, the only legitimate value of the second congruence is -1. This is something we should look for. If the second congruence $\displaystyle a^{\frac{n-1}{2}} \ (\text{mod} \ n)$ is not a -1, then choose another value of $a$ and start over. In fact, the second congruence should be the one to do first. If it is not a -1, then use another value of $a$.

Example 2

Using Lucas’ theorem, perform primality testing on the following number

$n=$ 3825123056546413183.

As a preliminary check, it is a strong probable prime to base 2. Next, factor $n-1$ as far as possible.

$n-1=2 \cdot 3 \cdot 11 \cdot 17 \cdot 211 \cdot 16157348744821$

The last factor $m=$ 16157348744821 of $n-1$ is an 14-digit number. It is a probable prime to base 2, meaning that $2^{m-1} \equiv 1 \ (\text{mod} \ m)$. So we have a good reason to believe that $m$ might be a prime. To test whether it is prime, we can use the same method to test. So now we focus our attention on the number $m=$ 16157348744821. Factor $m-1$ as far as possible.

$m-1=2^2 \cdot 3 \cdot 5 \cdot 31 \cdot 149 \cdot 58300313$

The last factor $T=$ 58300313 is a prime number. The square root of $T$ is 7635.46. None of the prime numbers below 7635 is a factor of $T$. So the above factorization is the prime factorization of $m-1$. We calculation the following:

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

$\displaystyle a^{\frac{m-1}{2}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{3}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{5}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{31}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{149}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{58300313}} \ (\text{mod} \ m)$

We use $a=2$ as a starting point. We have the following results.

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

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

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

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

$\displaystyle 2^{\frac{m-1}{31}} \equiv 8907135419651 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{149}} \equiv 4770370795536 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{58300313}} \equiv 13899477097778 \not \equiv 1 \ (\text{mod} \ m)$

We are lucky that the first $a$ we try works. Now we have proof that the number $m$ is a prime. As a result, the prime factorization of $n-1$ for the original number $n=$ 3825123056546413183 is complete. To prove the primality of $n$, we calculate the following.

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

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

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

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

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

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

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

We try $a=2$ and then $a=3$, both not working, with $\displaystyle 2^{\frac{n-1}{2}} \equiv 1 \ (\text{mod} \ n)$ and $\displaystyle 3^{\frac{n-1}{3}} \equiv 1 \ (\text{mod} \ n)$. Next we try $a=5$, with the following results.

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

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

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

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

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

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

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

The above calculation for base $a=5$ shows that the number $n=$ 3825123056546413183 is prime.

Example 3

Consider the number $n=$ 219944603708904241. The following is the factorization of $n-1$.

$n-1=2^4 \cdot 3^3 \cdot 5 \cdot 23 \cdot 3691 \cdot 1199465273$

The last factor $m=$ 1199465273 is a probable prime to base 2, meaning that $2^{m-1} \equiv 1 \ (\text{mod} \ m)$. We have good evidence that $m$ is prime. To confirm, we apply Lucas’ theorem on this number. The following is the prime factorization of $m-1$, where each factor is small and is easy to be determined as prime.

$m-1=2^3 \cdot 23 \cdot 677 \cdot 9629$

To prove the primality of $m$, we calculate the following.

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

$\displaystyle a^{\frac{m-1}{2}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{23}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{677}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{9629}} \ (\text{mod} \ m)$

We try two random choices for $a$ and do not have the desired results. The next random choice is $a=$ 526979896. The following calculation proves that $m$ is prime.

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

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

$\displaystyle a^{\frac{m-1}{23}} \equiv 820189482 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{677}} \equiv 695226481 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{9629}} \equiv 554335065 \not \equiv 1 \ (\text{mod} \ m)$

With the prime factorization of $n-1$ being complete, we turn our attention to the following calculations.

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

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

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

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

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

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

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

We generate the following 8 random choices of $a$

013397886753078290
193080712858269996
012695419760523254
096180046746919966
134541150430885987
212892893489065625
209448807773524821
141141720485036352

and find that $\displaystyle a^{\frac{n-1}{2}} \equiv 1 \ (\text{mod} \ n)$ for all these 8 values of $a$. This is highly unusual if the number $n$ is prime. We then realize that we forget to check for strong probable primality of $n$. With $n-1=2^4 \cdot Q$ where $Q=$ 13746537731806515, we calculate the following:

$\displaystyle 2^{Q} \equiv 123276781822261547 \ (\text{mod} \ n)$

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

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

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

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

The above calculation shows that the number $n=$ 219944603708904241 is composite; it is a strong pseudoprime to base 2. This goes to show that before applying Lucas’ theorem, it makes sense to do some strong probable prime test to rule out numbers that happen to be composite.

The number in Example 3 is a Carmichael number. It is the product of the prime factors $6m+1$, $12m+1$ and $18m+1$ where $m=$ 55365.

___________________________________________________________________

Exercises

Prove the compositeness or primality of each of the following numbers. In proving primality, use Lucas’ theorem as shown in the above examples.

204482919124364689
3825123056546413093
3825123056546413133
3825123056546413211
3825123056546413213

___________________________________________________________________

Reference

1. 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}$

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

A formula for generating strong pseudoprimes

We show in the previous post that $2^n-1$ is a strong pseudoprime to base 2 whenever $n$ is a pseudoprime to base 2. This formula establishes that there are infinitely many strong pseudoprime to base 2. Since the smallest pseudoprime to base 2 is 341, the smallest possible strong pseudoprime given by this formula is a 103-digit number. In this post, we discuss another formula that will generate some of the smaller strong pseudoprimes to base 2. We prove the following theorem.

Theorem 1
Let $p$ be a prime number that is larger than 5. Then the following number is a strong pseudoprime to base 2.

$\displaystyle M_p=\frac{4^p+1}{5}$

Proof of Theorem 1
First step is to show that $M_p$ is a composite number. Note that $4 \equiv -1 \ (\text{mod} \ 5)$. Then $4^p \equiv (-1)^p \equiv -1 \ (\text{mod} \ 5)$. This means that $4^p+1$ is divisible by 5. it follows that $M_p$ is an integer. Furthermore, the following product shows that $4^p+1$ is composite.

$\displaystyle 4^p+1=(2^p-2^{\frac{p+1}{2}}+1) \cdot (2^p+2^{\frac{p+1}{2}}+1)$

One of the above factors is divisible by 5. It is then clear that $M_p$ is composite.

On the other hand, the above factorization of $4^p+1$ implies that $2^{2p} \equiv -1 \ (\text{mod} \ M_p)$. Furthermore, for any odd integer $t$, we have $2^{2 \cdot p \cdot t} \equiv -1 \ (\text{mod} \ M_p)$.

Next the following computes $M_p-1$:

$\displaystyle M_p-1=\frac{4^p+1}{5}-1=\frac{4^p-4}{5}=4 \cdot \frac{4^{p-1}-1}{5}=2^2 \cdot q$

where $\displaystyle q=\frac{4^{p-1}-1}{5}$. Since $p$ is prime, we have $4^{p-1} \equiv 1 \ (\text{mod} \ p)$. This means that $4^{p-1}-1=p \cdot k$ for some integer $k$. Since 5 divides $p \cdot k$ and $p$ is a prime larger than 5, 5 must divides $k$. Thus $q=p \cdot t$ where $k=5t$. Since $q$ is odd, $t$ is odd too. Based on one earlier observation, $\displaystyle 2^{2 \cdot q} \equiv 2^{2 \cdot p \cdot t} \equiv -1 \ (\text{mod} \ M_p)$. It follows that $M_p$ is a strong pseudoprime to base 2. $\blacksquare$

___________________________________________________________________

Examples

The first several values of $M_p$ are:

$M_{7}=$ 3277

$M_{11}=$ 838861

$M_{13}=$ 13421773

$M_{17}=$ 3435973837

$M_{19}=$ 54975581389

$M_{23}=$ 14073748835533

$M_{29}=$ 57646075230342349

The formula $M_p$ captures more strong pseudoprimes than $2^n-1$. There are still many strong pseudoprimes that are missing. For example, according to [1], there are 4842 strong pseudoprimes to base 2 that are less than $25 \cdot 10^9$. The formula $M_p$ captures only 4 of these strong pseudoprimes. However, it is still valuable to have the formula $M_p$. It gives a concrete proof that there exist infinitely many strong pseudoprimes to base 2. Strong pseudoprimes are rare. It is valuable to have an explicit formula to generate examples of strong pseudoprimes. For example, $M_{19}$ is the first one on the list that is larger than $25 \cdot 10^9$. Then $M_{19}$ is an upper bound on the least strong pseudoprime base 2 that is larger than $25 \cdot 10^9$.

___________________________________________________________________

Question

It is rare to find strong pseudoprimes to multiple bases. For example, according to [1], there are only 13 strong pseudoprimes to all of the bases 2, 3 and 5 that are less than $25 \cdot 10^9$. Are there any strong pseudoprimes given by the formula $M_p$ that are also strong pseudoprimes to other bases? What if we just look for pseudoprimes to other bases?

___________________________________________________________________

Reference

1. 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}$

There are infinitely many strong pseudoprimes

Pseudoprimes are rare. Strong pseudoprimes are rarer still. According to [1], there are 21853 pseudoprimes to base 2 and 4842 strong pseudoprimes to base 2 below $25 \cdot 10^9$. According to the prime number theorem, there are over 1 billion prime numbers in the same range. When testing a random number, knowing that it is a strong probable prime to just one base is strong evidence for primality. Even though most of the strong probable primes are prime, for a given base, there exist infinitely many strong pseudoprimes. This fact is captured in the following theorem.

Theorem 1
For a given base $a>1$, there are infinitely many strong pseudoprimes to base $a$.

For a proof, see Theorem 1 in [1]. We give a simpler proof that there exist infinitely many strong pseudoprimes to base 2.

Theorem 1a
There are infinitely many strong pseudoprimes to base 2.

Proof of Theorem 1a
We make the following claim.

Claim
Let $n$ be a pseudoprime to base 2. Then $N=2^n-1$ is a strong pseudoprime to base 2.

In a previous post on probable primes and pseudoprimes, we prove that there exist infinitely pseudoprimes to any base $a$. Once the above claim is established, we have a proof that there are infinitely many strong pseudoprimes to base 2.

First of all, if $n$ is composite, the number $2^n-1$ is also composite. This follows from the following equalities.

$\displaystyle 2^{ab}-1=(2^a-1) \cdot (1+2^a+2^{2a}+2^{3a}+ \cdots+2^{(b-1)a})$

$\displaystyle 2^{ab}-1=(2^b-1) \cdot (1+2^b+2^{2b}+2^{3b}+ \cdots+2^{(a-1)b})$

Thus $N=2^n-1$ is composite. Note that $N-1=2^n-2=2 \cdot (2^{n-1}-1)$. Let $q=2^{n-1}-1$, which is an odd integer. Because $n$ is a pseudoprime to base 2, $2^{n-1} \equiv 1 \ (\text{mod} \ n)$. Equivalently, $2^{n-1}-1=nj$ for some integer $j$. Furthermore, it is clear that $2^{n} \equiv 1 \ (\text{mod} \ 2^n-1)$.

It follows that $\displaystyle 2^q \equiv 2^{2^{n-1}-1} \equiv 2^{nj} \equiv 1^j \equiv 1 \ (\text{mod} \ N)$. This means that $N$ is a strong pseudoprime to base 2.

In the previous post probable primes and pseudoprimes, it is established that there are infinitely many pseudoprimes to any base $a$. In particular there are infinitely many pseudoprimes to base 2. It follows that the formula $2^n-1$ gives infinitely many strong pseudoprimes to base 2. $\blacksquare$

___________________________________________________________________

Example

Theorem 1a can be considered a formula for generating strong pseudoprimes to base 2. The input is a pseudoprime to base 2. Unfortunately the generated numbers get large very quickly and misses many strong pseudoprimes to base 2.

The smallest pseudoprime to base 2 is 341. The following is the 103-digit $N=2^{341}-1$.

$N=2^{341}-1=$
44794894843556084211148845611368885562432909944692
99069799978201927583742360321890761754986543214231551

Even though $N=2^{341}-1$ is a strong pseudoprime to base 2, it is not strong pseudoprime to bases 3 and 5. In fact, it is rare to find a strong pseudoprime to multiple bases. To determine the strong pseudoprimality of $N$ for other bases, note that $N-1=2 \cdot Q$ where $Q$ is the following 103-digit number.

$Q=$
22397447421778042105574422805684442781216454972346
49534899989100963791871180160945380877493271607115775

Calculate $a^Q$ and $a^{2Q}$ modulo $N$. Look for the pattern $a^Q=1$ and $a^{2Q}=1$ or the pattern pattern $a^Q=-1$ and $a^{2Q}=1$. If either pattern appears, then $N$ is a strong pseudoprime to base $a$. See the sequence labeled (1) in the previous post on strong pseudoprimes.

___________________________________________________________________

Exercise

Verify that $N=2^{341}-1$ is not a strong pseudoprime to both bases 3 and 5.

___________________________________________________________________

Reference

1. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to $25 \cdot 10^9$, Math. Comp., Volume 35, 1003-1026, 1980.

___________________________________________________________________
$\copyright \ \ 2014-2015 \ \text{Dan Ma}$
Revised July 4, 2015

Strong probable primes and strong pseudoprimes

This post is the first in a series of posts to discuss the Miller-Rabin primality test. In this post, we discuss how to perform the calculation (by tweaking Fermat’s little theorem). The Miller-Rabin test is fast and efficient and is in many ways superior to the Fermat test.

Fermat primality test is based on the notions of probable primes and pseudoprimes. One problem with the Fermat test is that it fails to detect the compositeness of a class of composite numbers called Carmichael numbers. It is possible to tweak the Fermat test to by pass this problem. The resulting primality test is called the Miller-Rabin test. Central to the working of the Miller-Rabin test are the notions of strong probable primes and strong pseudoprimes.

Fermat’s little theorem, the basis of the Fermat primality test, states that if $n$ is a prime number, then

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

for all numbers $a$ that are relatively prime to the modulus $n$. When testing a prime number, the Fermat test always gives the correct answer. What is the success rate of the Fermat test when it is applied on a composite number? The Fermat test is correct on most composite numbers. Unfortunately the Fermat test fails to detect the compositeness of Carmichael numbers. A Carmichael number is any composite integer $n$ such that (*) is true for any $a$ that is relatively prime to $n$. Fortunately we can tweak the calculation in (*) to get a better primality test.

Recall that a positive odd integer $n$ is a probable prime to base $a$ if the condition (*) holds. A probable prime could be prime or could be composite. If the latter, then $n$ is said to be a pseudoprime to base $a$.

___________________________________________________________________

Setting up the calculation

Let $n$ be an odd positive integer. Instead of calculating $a^{n-1} \ (\text{mod} \ n)$, we set $n-1=2^k \cdot q$ where $q$ is an odd number and $k \ge 1$. Then compute the following sequence of $k+1$ numbers:

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

Each term in (1) is reduced modulo $n$. The first term can be computed using the fast powering (also called fast exponentiation) algorithm. Each subsequent term is the square of the preceding term. Of course, the last term is $a^{2^{k} q}=a^{n-1}$. It follows from Fermat’s little theorem that the last term in the sequence (1) is always a 1 as long as $n$ is prime and the number $a$ is relatively prime to $n$. The numbers $a$ used in the calculation of (1) are called bases.

Suppose we have a large positive odd integer $n$ whose “prime or composite” status is not known. Choose a base $a$. Then compute the numbers in the sequence (1). If $n$ is prime, we will see one of the following two patterns:

$1, 1, 1, \cdots, 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1a)$

$*, *, *, \cdots, *, -1, 1, \cdots, 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1b)$

In (1a), the entire sequence consists of 1. In (1b), an asterisk means that the number is congruent to neither 1 nor -1 modulo $n$. In (1b), the sequence ends in a 1, and the term preceding the first 1 is a -1. These two patterns capture a property of prime numbers. We have the following theorem.

___________________________________________________________________

The theorem behind the Miller-Rabin test

Theorem 1
Let $n$ be an odd prime number such that $n-1=2^k \cdot q$ where $q$ is an odd number and $k \ge 1$. Let $a$ be a positive integer not divisible by $n$. Then the sequence (1) resembles (1a) or (1b), i.e., either one of the following two conditions holds:

• The first term $a^q$ in the sequence (1) is congruent to 1 modulo $n$.
• The term preceding the first 1 is congruent to -1 modulo $n$.

The proof of Theorem 1 is not complicated. It uses Fermat’s little theorem and the fact that if $n$ is an odd prime, the only solutions to the congruence equation $x^2 \equiv 1 \ (\text{mod} \ n)$ are $x \equiv \pm 1 \ (\text{mod} \ n)$. The proof goes like this. By Fermat’s little theorem, the last term in sequence (1) is a 1, assuming that $n$ is an odd prime and $a$ is relatively prime to $n$. If the first term in (1) is a 1, then we are done. Otherwise, look at the first term in (1) that is a 1. The term preceding the first 1 must be a -1 based on the fact that the equation $x^2 \equiv 1 \ (\text{mod} \ n)$ can have only the trivial solutions $\pm 1$.

It is an amazing fact that Theorem 1 is easily proved and yet is the basis of a powerful and efficient and practical primality test. Next we define the notions of strong probable primes and strong pseudoprimes.

___________________________________________________________________

Strong probable primes and strong pseudoprimes

Suppose we have a large positive odd integer $n$ whose “prime or composite” status is not known. We calculate sequence (1) for one base $a$. If the last term of the sequence (1) is not a 1, then $n$ is composite by Fermat’s little theorem. If the last term is a 1 but the sequence (1) does not match the patterns (1a) or (1b), then $n$ is composite by Theorem 1. So to test for compositeness for $n$, we look for a base $a$ such that the sequence (1) does not fit the patterns (1a) or (1b). Such a base is said to be a Miller-Rabin witness for the compositeness of $n$. Many authors refer to a Miller-Rabin witness as a witness.

When we calculate the sequence (1) on the odd number $n$ for base $a$, if we get either (1a) or (1b), then $n$ is said to be a strong probable prime to the base $a$. A strong probable prime could be prime or could be composite. When a strong probable prime to the base $a$ is composite, it is said to be a strong pseudoprime to the base $a$. To test for primality of $n$, the Miller-Rabin test consists of checking for strong probable primality for several bases $a$ where $1 that are randomly chosen.

For an example of a primality testing exercise using the Miller-Rabin test, see the post The first prime number after the 8th Fermat number.

___________________________________________________________________

Small examples of strong pseudoprimes

Some small examples to illustrate the definitions. Because $2^{340} \equiv 1 \ (\text{mod} \ 341)$, the number 341 is a probable prime to the base 2. Because 341 is composite with factors 11 and 31, the number 341 is a pseudoprime to the base 2. In fact, 341 is the least pseudoprime to base 2. Now the strong probable prime calculation. Note that $341=2^2 \cdot 85$. The calculated numbers in sequence (1) are 32, 1, 1, calculated as follows:

$2^{85} \equiv 32 \ (\text{mod} \ 341)$

$2^{2 \cdot 85} \equiv 32^2 \equiv 1 \ (\text{mod} \ 341)$

$2^{340}=2^{2 \cdot 85} \equiv 1 \ (\text{mod} \ 341)$

Because the sequence 32, 1, 1 does not fit pattern (1a) or (1b) (the term before the first 1 is not a -1), the number 341 is not a strong pseudoprime prime to base 2.

How far do we have to go up from 341 to reach the first strong pseudoprime to base 2. The least strong pseudoprime to base 2 is 2047. Note that $2046=2 \cdot 1023$. Note that the congruences $2^{1023} \equiv 1 \ (\text{mod} \ 2047)$ and $2^{2046} \equiv 1 \ (\text{mod} \ 2047)$. The sequence (1) is 1, 1, which is the pattern (1a). Thus 2047 is a strong pseudoprime to base 2. Note that 2047 is composite with factors 23 and 89. It can be shown (at least by calculation) that all odd integers less than 2047 are not strong pseudoprime to base 2. In other words, if a positive odd integer $n$ is less than 2047 and if it is a strong probable prime to base 2, then $n$ must be a prime number.

Consider a slightly larger example. Let $n=$ 65281. Set $n-1=2^{8} \cdot 255$. The following is the calculation for the sequence (1) using base 2.

$2^{255} \equiv 32768 \ (\text{mod} \ 65281)$

$2^{2 \cdot 255} \equiv 65217 \ (\text{mod} \ 65281)$

$2^{4 \cdot 255} \equiv 4096 \ (\text{mod} \ 65281)$

$2^{8 \cdot 255} \equiv 65280 \equiv -1 \ (\text{mod} \ 65281)$

$2^{16 \cdot 255} \equiv 1 \ (\text{mod} \ 65281)$

$2^{32 \cdot 255} \equiv 1 \ (\text{mod} \ 65281)$

$2^{64 \cdot 255} \equiv 1 \ (\text{mod} \ 65281)$

$2^{128 \cdot 255} \equiv 1 \ (\text{mod} \ 65281)$

$2^{256 \cdot 255} \equiv 1 \ (\text{mod} \ 65281)$

The pattern is *, *, *, -1, 1, 1, 1, 1, 1, which is (1b) (the term preceding the first 1 is a -1). So $n=$ 65281 is strong probable prime to base 2. The following computation using base 3 will show that 65281 is a composite number, thus is a strong pseudoprime to base 2.

$3^{255} \equiv 30931 \ (\text{mod} \ 65281)$

$3^{2 \cdot 255} \equiv 33706 \ (\text{mod} \ 65281)$

$3^{4 \cdot 255} \equiv 9193 \ (\text{mod} \ 65281)$

$3^{8 \cdot 255} \equiv 37635 \ (\text{mod} \ 65281)$

$3^{16 \cdot 255} \equiv 56649 \ (\text{mod} \ 65281)$

$3^{32 \cdot 255} \equiv 25803 \ (\text{mod} \ 65281)$

$3^{64 \cdot 255} \equiv 59171 \ (\text{mod} \ 65281)$

$3^{128 \cdot 255} \equiv 56649 \ (\text{mod} \ 65281)$

$3^{65280} = 3^{256 \cdot 255} \equiv 25803 \ (\text{mod} \ 65281)$

Looking at the last term in the base 3 calculation, we see that the number 65281 is composite by Fermat’s little theorem. Because the pattern is *, *, *, *, *, *, *, *, *, 65281 is not a strong pseudoprime to base 3.

___________________________________________________________________

How does pseudoprimality and strong pseudoprimality relate?

There are two notions of “pseudoprime” discussed here and in previous posts. One is based on Fermat’s little theorem (pseudoprime) and one is based on Theorem 1 above (strong pseudoprime). It is clear from the definition that any strong pseudoprime to base $a$ is a pseudoprime to base $a$. The converse is not true.

Let’s start with the number 341. It is a pseudoprime to base 2. This means that the Fermat test cannot detect its compositeness using base 2. Yet the strong pseudoprimality calculation as described above can detect the compositeness of 341 using base 2. The 341 is not a strong pseudoprime to base 2 since the least strong pseudoprime to base 2 is 2047.

Let’s look at a slightly larger example. Take the number 25761. It is a pseudoprime to base 2 since $2^{25760} \equiv 1 \ (\text{mod} \ 25761)$ and its factors are 3, 31 and 277. Let refine the calculation according to sequence (1) as indicated above. Note that $25760=2^5 \cdot 805$. The pattern of sequence (1) is *, *, 1, 1, 1, 1. The term preceding the first 1 is not a -1. Thus the strong pseudomality method does detect the compositeness of 25761 using base 2.

In general, strong pseudoprimality implies pseudoprimality (to the same base). The above two small examples show that the converse is not true since they are pseudoprimes to base 2 but not strong pseudoprimes to base 2.

___________________________________________________________________

Why look at pseudoprimes and strong pseudoprimes?

The most important reason for studying these notions is that pseudoprimality and strong pseudoprimality are the basis of two primality tests. In general, pseudoprimality informs primality.

In a previous post on probable primes and pseudoprimes, we point out that most probable primes are primes. The same thing can be said for the strong version. According to [1], there are only 4842 strong pseudoprimes to base 2 below $25 \cdot 10^9$. Using the prime number theorem, it can be shown that there are approximately $1.044 \cdot 10^9$ many prime numbers below $25 \cdot 10^9$. Thus most strong probable primes are primes. For a randomly chosen $n$, showing that $n$ is a strong probable prime to one base can be quite strong evidence that $n$ is prime.

Because strong pseudoprimality is so rare, knowing what they are actually help in detecting primality. For example, according to [1], there are only 13 numbers below $25 \cdot 10^9$ that are strong pseudoprimes to all of the bases 2, 3 and 5. These 13 strong pseudoprimes are:

Strong pseudoprimes to all of the bases 2, 3 and 5 below 25 billion

25326001, 161304001, 960946321, 1157839381, 3215031751, 3697278427, 5764643587, 6770862367, 14386156093, 15579919981, 18459366157, 19887974881, 21276028621

These 13 strong pseudoprimes represent a deterministic primality test on integers less than $25 \cdot 10^9$. Any odd positive integer less than $25 \cdot 10^9$ that is a strong probable prime to all 3 bases 2, 3 and 5 must be a prime number if it is not one of the 13 numbers on the list. See Example 1 below for an illustration. This primality is fast since it only requires 3 exponentiations. Best of all, it gives a proof of primality. However, this is a fairly limited primality test since it only works on numbers less than $25 \cdot 10^9$. Even though this is a limited example, it is an excellent illustration that strong pseudoprimality can inform primality.

Example 1
Consider the odd integer $n=$ 1777288949, which is less than $25 \cdot 10^9$. Set $1777288949=2^2 \cdot 444322237$. The proof of primality of requires only the calculation for 3 bases 2, 3 and 5.

Base 2

$2^{444322237} \equiv 227776882 \ (\text{mod} \ 1777288949)$

$2^{2 \cdot 444322237} \equiv 1777288948 \equiv -1 \ (\text{mod} \ 1777288949)$

$2^{2^2 \cdot 444322237} \equiv 1 \ (\text{mod} \ 1777288949)$

Base 3

$3^{444322237} \equiv 227776882 \ (\text{mod} \ 1777288949)$

$3^{2 \cdot 444322237} \equiv 1777288948 \equiv -1 \ (\text{mod} \ 1777288949)$

$3^{2^2 \cdot 444322237} \equiv 1 \ (\text{mod} \ 1777288949)$

Base 5

$5^{444322237} \equiv 1 \ (\text{mod} \ 1777288949)$

$5^{2 \cdot 444322237} \equiv 1 \ (\text{mod} \ 1777288949)$

$5^{2^2 \cdot 444322237} \equiv 1 \ (\text{mod} \ 1777288949)$

The patterns for the 3 calculations fit either (1a) or (1b). So $n=$ 1777288949 is a strong probable prime to all 3 bases 2, 3 and 5. Clearly $n=$ 1777288949 is not on the list of 13 strong pseudoprimes listed above. Thus $n=$ 1777288949 cannot be a composite number.

___________________________________________________________________

Exercise

• Use the strong pseudoprime test to show that the following numbers are composite.
• 3277
43273
60433
60787
838861
1373653

• Use the 13 strong pseudoprimes to the bases 2, 3 and 5 (used in Example 1) to show that the following numbers are prime numbers.
• 58300313
99249929
235993423
2795830049

___________________________________________________________________

Reference

1. 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}$