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<k$ . 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.

The Jacobi symbol $(\frac{r}{a})=-1$ for all Fermat remainders $r$ modulo $a$ .
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.

The Legendre symbol $(\frac{r}{p})=-1$ for all Fermat remainders $r$ modulo $p$ .
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.

For each Fermat remainders $r$ modulo $p$ , $r$ is a quadratic nonresidue modulo $p$
For each Fermat remainders $r$ modulo $p$ , the congruence $r^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ holds.
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$

$F_1 \equiv$

$F_2 \equiv$

$F_3 \equiv$

$F_4 \equiv$

$F_5 \equiv$

$F_6 \equiv$

$F_7 \equiv$

$F_8 \equiv$

$F_9 \equiv$

$F_{10} \equiv$

$F_{11} \equiv$

$F_{12} \equiv$

$F_{13} \equiv$

$F_{14} \equiv$

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

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$

$F_1 \equiv$

$F_2 \equiv$

$F_3 \equiv$

$F_4 \equiv$

$F_5 \equiv$

$F_6 \equiv$

$F_7 \equiv$

$F_8 \equiv$

$F_9 \equiv$

$F_{10} \equiv$

$F_{11} \equiv$

$F_{12} \equiv$

$F_{13} \equiv$

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

Mathematical Cryptography

focusing on the math in public key cryptography

Pepin’s Primality Test

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply