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