Strong probable primes and strong pseudoprimes

Posted on November 18, 2014 by Dan Ma

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

$n$

$n-1=2^k \cdot q$

$q$

$k \ge 1$

$a$

$n$

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<a<n$ 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.

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

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

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

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.

___________________________________________________________________

Reference

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

The Fermat primality test

Posted on November 11, 2014 by Dan Ma

Fermat’s little theorem describes a property that is common to all prime numbers. This property can be used as a way to detect the “prime or composite” status of an integer. Primality testing using Fermat’s little theorem is called the Fermat primality test. In this post, we explain how to use this test and to discuss some issues surrounding the Fermat test.

___________________________________________________________________

Describing the test

The Fermat primality test, as mentioned above, is based on Fermat’s little theorem. The following is the statement of the theorem.

Fermat’s little theorem

$n$

$a$

$n$

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

The above theorem indicates that all prime numbers possess a certain property. Therefore if a given positive integer does not possess this property, we know for certain that this integer is not prime. Suppose that the primality of an integer $n$ is not known. If we can find an integer $a$ that is relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ , then we have conclusive proof that $n$ is composite. Such a number $a$ is said to be a Fermat witness for (the compositeness of) $n$ .

The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for $n$ and $a$ , then $n$ is said to be a probable prime to base $a$ . Furthermore, if $n$ happens to be a composite number, then $n$ is said to be a pseudoprime to base $a$ . Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base $a$ .

The Fermat primality test from a compositeness perspective is about looking for Fermat witnesses. If a Fermat witness is found, the number being tested is proved to be composite. On the other hand, the Fermat primality test, from a primality perspective, consists of checking the congruence relation (1) for several bases that are randomly selected. If the number $n$ is found to be a probable prime to all the randomly chosen bases, then $n$ is likely a prime number.

If the number $n$ is in reality a prime number, then the Fermat test will always give the correct result (as a result of Fermat’s little theorem). If the number $n$ is in reality a composite number, the Fermat test can make the mistake of identifying the composite number $n$ as prime (i.e. identifying a pseudoprime as a prime). For most composite numbers this error probability can be made arbitrarily small (by testing a large number of bases $a$ ). But there are rare composite numbers that evade the Fermat test. Such composite numbers are called Carmichael numbers. No matter how many bases you test on a Carmichael number, the Fermat test will always output Probably Prime. Carmichael numbers may be rare but there are infinitely many of them over the entire number line. More about Carmichael numbers below.

The following describes the steps of the Fermat primality test.

Fermat primality test

$n$

Composite

$n$

Probably Prime

Step 1. Choose a random integer $a \in \left\{2,3,\cdots,n-1 \right\}$ .
Step 2. Compute $\text{GCD}(a,n)$ . If it is greater than 1, then stop and output $n$ is Composite. Otherwise go to the next step.
Step 3. Compute $a^{n-1} \ (\text{mod} \ n)$ .

If $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ , then stop and output $n$ is Composite.
If $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ , then $n$ may be a prime number. Do one of the following:

Return to Step 1 and repeat the process with a new $a$ .
Output $n$ is Probably Prime and stop.

$\text{ }$

The exponentiation in Step 3 can be done by the fast powering algorithm. This involves a series of squarings and multiplications. Even for numbers that have hundreds of digits, the fast powering algorithm is efficient.

One comment about Step 2 in the algorithm. Step 2 could be called the GCD test for primality. If you can find an integer $a$ such that $1<a<n$ and such that $\text{GCD}(a,n) \ne 1$ , then the integer $n$ is certainly composite. Such a number $a$ is called a GCD witness for the compositeness of $n$ . So the Fermat test as described above combines the GCD test and the Fermat test. We can use the Euclidean algorithm to find the GCD. If we happen to stumble upon a GCD witness, then we can try another $n$ for a candidate of a prime number. For most composite numbers, it is not likely to stumble upon a GCD witness. Thus when using the Fermat test, it is likely that Step 3 in the algorithm is used.

An example of Fermat primality testing is the post called A primality testing exercise from RSA-100.

____________________________________________________________________________

More about the test

When using the Fermat test, what is the probability of the test giving the correct result? Or what is the probability of making an error? Because the Fermat test is not a true probabilistic primality test, the answers to these questions are conditional. In one scenario which covers most of the cases, the test works like an efficient probabilistic test. In another scenario which occurs very rarely, the Fermat test fails miserably.

As with most diagnostic tests, the Fermat test can make two types of mistakes – false positives or false negatives. For primality testing discussed in this post, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number.

For the Fermat test, there is no false negative. If $n$ is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that $n$ be declared a composite number. Thus if the Fermat test gives a negative result, it would be a true negative. In other words, finding a Fermat witness for $n$ is an irrefutable proof that $n$ is composite.

However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number $n$ is said to be a Carmichael number if the above congruence relationship (1) holds for all bases $a$ relatively prime to $n$ . In other words, $n$ is a Carmichael number if $a^{n-1} \equiv 1 (\text{mod} \ n)$ for all $a$ that are relatively prime to $n$ . Saying it in another way, $n$ is a Carmichael number if there exists no Fermat witness for $n$ .

The smallest Carmichael number is 561. Carmichael numbers are rare but there are infinitely many of them. The existence of such numbers poses a challenge for the Fermat test. If you apply the Fermat test on a Carmichael number, the outcome will always be Probably Prime. So the Fermat test will always give a false positive when it is applied on a Carmichael number. To put it in another way, with respect to Carmichael numbers, the error probability of the Fermat test is virtually 100%!

So should a primality tester do? To keep things in perspective, Carmichael numbers are rare (see this post). If the primality testing is done on randomly chosen numbers, choosing a Carmichael number is not likely. So the Fermat test will often give the correct results. For those who are bothered by the nagging fear of working with Carmichael numbers, they can always switch to a Carmichael neutral test such as the Miller-Rabin test.

___________________________________________________________________

One bright spot about the Fermat test

There is one bright spot about the Fermat test. When applying the Fermat test on numbers that are not Carmichael numbers, the error probability can be made arbitrarily small. In this sense the Fermat test works like a true probabilistic primality test. Consider the following theorem.

Theorem 1

$n$

$a$

$1<a<n$

$n$

$a$

$1<a<n$

$n$

Theorem 1 means that the Fermat test can be very accurate on composite numbers that are not Carmichael numbers. As long as there is one base to which the composite number is not a pseudoprime (i.e. as long as there is a Fermat witness for the composite number in question), there will be enough of such bases (at least 50% of the possible bases). As a result, it is likely that the Fermat test will find a witness, especially if the tester is willing to use enough bases to test and if the bases are randomly chosen. When a base is randomly chosen, there is at least a 50% chance that the number $n$ is not a pseudoprime to that base (i.e. the Fermat test will detect the compositeness) or putting it in another way, there is at most a 50% chance that the Fermat test will not detect the compositeness of the composite number $n$ . So if $k$ values of $a$ are randomly selected, there is at most $0.5^k$ probability that the Fermat test will not detect the compositeness of the composite number $n$ (i.e. making a mistake). So the probability of a false positive is at most $0.5^k$ . For a large enough $k$ , this probability is practically zero.

Proof of Theorem 1
A base to which $n$ is a pseudoprime or not a pseudoprime should be a number in the interval $1<a<n$ that is relatively prime to $n$ . If $n$ is a pseudoprime to base $a$ , then $a$ raised to some power is congruent to 1 modulo $n$ . For this to happen, $a$ must be relatively prime to the modulus $n$ . For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer $n$ (see the post on Euler’s phi function).

Let $a$ be a base to which $n$ is not a pseudoprime. We make the following claim.

Claim

$b$

$1<b<n$

$n$

$b$

$n$

$a \cdot b$

Since both integers $a$ and $b$ are assumed to be relatively prime to $n$ , the product $a \cdot b$ is also relatively prime to $n$ (see Lemma 4 in this post). Now consider the congruence $(ab)^{n-1} \ (\text{mod} \ n)$ , which is derived as follows:

$(ab)^{n-1} \equiv a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$

In the above derivation, we use the fact that $n$ is not a pseudoprime to base $a$ and $n$ is a pseudoprime to base $b$ . The above derivation shows that $n$ is not a pseudoprime to base $ab$ .

If $n$ is not a pseudoprime to all bases in $1<w<n$ , then we are done. So assume that $n$ is a pseudoprime to at least one base. Let $b_1,b_2,\cdots,b_k$ enumerate all bases to which $n$ is a pseudoprime. We assume that the $b_j$ are all distinct. So $b_i \not \equiv b_j \ (\text{mod} \ n)$ for all $i \ne j$ . By the above claim, the composite number $n$ is not a pseudoprime to all the following $k$ numbers:

$a \cdot b_1, \ a \cdot b_2, \cdots, \ a \cdot b_k$

It is also clear that $a \cdot b_i \not \equiv a \cdot b_j \ (\text{mod} \ n)$ for $i \ne j$ . What we have just shown is that there are at least as many bases to which $n$ is not a pseudoprime as there are bases to which $n$ is a pseudoprime. This means that $n$ is not a pseudoprime to at least 50% of the bases that are relatively prime to $n$ . In other words, as long as there exists one Fermat witness for $n$ , at least 50% of the bases are Fermat witnesses for $n$ . It then follows that $n$ is a pseudoprime to no more than 50% of the bases relatively prime to $n$ . $\blacksquare$

There is another way to state Theorem 1. Recall that Euler’s phi function $\phi(n)$ is defined to be the number of integers $a$ in the interval $1<a<n$ that are relatively prime to $n$ . With this in mind, Theorem 1 can be restated as the following:

Corollary 2

$n$

$\displaystyle \frac{\phi(n)}{2}$

$1<a<n$

___________________________________________________________________

Concluding remarks

Of course, Theorem 1 works only for the composite numbers that are not pseudoprime to at least one base (i.e. they are not Carmichael numbers). When you test the compositeness of a number, you do not know in advance if it is Carmichael or not. On the other hand, if the testing is done on randomly chosen numbers, it is not likely to randomly stumble upon Carmichael numbers. The Fermat test works well for the most part and often give the correct results. If one is concerned about the rare chance of a false positive in the form of a Carmichael number, then the Miller-Rabin test will be a good alternative.

___________________________________________________________________
$\copyright \ \ 2014 - 2015 \ \text{Dan Ma}$ (Revised march 29, 2015)

Probable primes and pseudoprimes

Posted on November 11, 2014 by Dan Ma

In determining whether an odd integer $n$ is prime or composite, the author of this blog likes to first look for small prime factors of $n$ . If none is found, then calculate the congruence $2^{n-1} \ (\text{mod} \ n)$ . If this result is not congruent to 1 modulo $n$ , this gives a proof that $n$ is a composite number. If the result is congruent to 1, then this gives some evidence that $n$ is prime. To confirm, apply a formal primality test on the number $n$ (e.g. using the Miller-Rabin test). The question we like to ponder in this post is this. Given the result $2^{n-1} \equiv 1 \ (\text{mod} \ n)$ , as evidence for the primality of the number $n$ , how strong is it? Could we just use the congruence $2^{n-1} \ (\text{mod} \ n)$ as a primality test? In this post, we look at these questions from two perspectives, leading to two answers that are both valid in some sense. The discussion is conducted through examining the notions of probable primes and pseudoprimes, both of which are concepts that are related to Fermat’s little theorem. Thus the notions of probable primes and pseudoprimes are related to the Fermat primality test.

Fermat’s little theorem states that if $n$ is a prime number, then the following congruence

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

is always true for any integer $a$ that is relatively prime to $n$ . A positive integer $n$ is said to be a probable prime to the base $a$ if the congruence relation (1) holds. Obviously any prime number is a probable prime to all bases that are relatively prime to it (this is another way of stating Fermat’s little theorem). A probable prime does not have to be prime. If $n$ is a probable prime to base $a$ and if $n$ happens not to be prime, then $n$ is said to be a pseudoprime to base $a$ .

As indicated at the beginning, computing the congruence (1) for just one base $a$ is a quick and dirty way of checking probable primality of $n$ . Using base 2 as a starting point, if $2^{n-1}$ is not congruent to 1 mod $n$ , we know $n$ is composite for sure. If $2^{n-1}$ is congruent to 1 mod $n$ , then we can calculate the congruence for several more bases. The following question is similar to the questions at the beginning:

$a$

$n$

We look at this question from two angles. One is to answer in terms of an absolute mathematical proof. One is to look at it probabilistically.

___________________________________________________________________

The view point of an absolute mathematical proof

In terms of an absolute mathematical proof, the answer to the above question is no. There are probable primes that are composite (i.e. there are pseudoprimes). For example, the integer 341 is a probable prime to base 2 since $2^{340} \equiv 1 \ (\text{mod} \ 341)$ . But 341 is composite with factors 11 and 31. So 341 is a pseudoprime to the base 2. In fact, 341 is the least integer that is a pseudoprime to base 2. However, 341 is not a pseudoprime to the base 3 since $3^{340} \equiv 56 \ (\text{mod} \ 341)$ .

Now let $n$ be 1105, which obviously is composite since it ends in the digit 5. The number 1105 is a probable prime to both base 2 and base 3, since we have $2^{1104} \equiv 1 \ (\text{mod} \ 1105)$ and $3^{1104} \equiv 1 \ (\text{mod} \ 1105)$ . In fact, 1105 is the least integer that is a pseudoprime to both base 2 and base 3.

Furthermore, given a base $a$ , there are infinitely many pseudoprimes to base $a$ . We prove the following theorem.

Theorem 1
Let $a$ be any integer with $a>1$ . Then there are infinitely many pseudoprimes to base $a$ .

Proof
Let $p$ be an odd prime number such that $p$ does not divide $a^2-1$ and such that $p$ does not divide $a$ . We define a composite integer $m_p$ such that $a^{m_p-1} \equiv 1 \ (\text{mod} \ m_p)$ . We will see that the numbers $m_p$ are distinct for distinct primes $p$ . Clearly there are infinitely many odd primes $p$ that do not divide both $a^2-1$ and $a$ . The theorem will be established once we provide the details for these claims.

Fix an odd prime $p$ such that $p$ does not divide $a^2-1$ and such that $p$ does not divide $a$ . Define $m=m_p$ as follows:

$\displaystyle m=\frac{a^{2p}-1}{a^2-1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

The number $m$ is composite since it can be expressed as follows:

$\displaystyle m=\frac{a^{p}-1}{a-1} \times \frac{a^{p}+1}{a+1}$

Note that both factors in the above expression are integers. This is because the numerators can be expressed as:

$a^p-1=(a-1) \times (a^{p-1}+a^{p-2} + a^{p-3} + \cdots + a + 1)$

$a^p+1=(a+1) \times (a^{p-1}-a^{p-2} + a^{p-3} - \cdots - a + 1)$

Furthermore, the number $m$ is an odd integer. Note that $m$ is the product of the following two numbers $S$ and $T$ :

$S=a^{p-1}+a^{p-2} + a^{p-3} + \cdots + a + 1$

$T=a^{p-1}-a^{p-2} + a^{p-3} - \cdots - a + 1$

Both $S$ and $T$ are odd numbers. If $a$ is even, it is clear that both $S$ and $T$ are odd. If $a$ is odd, each of $S$ and $T$ is sum of even number of odd numbers plus 1, thus an odd number. Since $m$ is the product of two odd numbers, it is an odd number.

Now we need to show that $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ . From the definition of the number $m$ (see (*) above), we can derive the following:

$(a^2-1) (m-1)=a(a^{p-1}-1)(a^p+a)$

The term $a^{p-1}-1$ in the middle of the right hand side is divisible by $p$ because of Fermat’s little theorem. Therefore $p$ divides $(a^2-1)(m-1)$ . Since $p$ does not divide $a^2-1$ , $p$ must divide $m-1$ . Since $m$ is odd, $m-1$ must be even. Consequently $2p$ divides $m-1$ .

From the definition of the number $m$ ,we have $a^{2p}=1+m(a^2-1)$ . This is the same as saying $a^{2p} \equiv 1 \ (\text{mod} \ m)$ . Since $2p$ divides $m-1$ , we have $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ too.

It is clear that the numbers $m=m_p$ are different for different $p$ . Since there are infinitely many odd primes $p$ that do not divide both $a^2-1$ and $a$ , the theorem is established. $\blacksquare$

It is interesting that the proof of Theorem 1 is a constructive one. The formula (*) gives us a way to generate pseudoprime to base $a$ . For base 2, the first few pseudoprimes from this formula are 341, 5461, 1398101, 22369621. For base 3, the first few pseudoprimes are 91, 7381, 597871, 3922632451. However, the formula (*) does not generate all pseudoprimes for a given base. For example, 561 is a pseudoprime base 2 that is not generated by the formula. There are 19 pseudoprimes base 3 in between 91 and 7381 that are not captured by this formula. For the reason, the formula (*) is useful for proving theorem rather than for computing pseudoprimes.

So from a mathematical standpoint, computing the congruence (1) for one base is not sufficient evidence for primality. There are simply two many counterexamples, in fact infinitely many. So in deciding whether an integer $n$ is prime or not, knowing that it is a probable prime to one base is definitely not a proof to the primality of $n$ . But this is not the end of the story. There is another view.

___________________________________________________________________

The probabilistic view

By Theorem 1, there are infinitely many pseudoprimes to base $a$ . So showing that an integer $n$ is a probable prime to one base $a$ is no proof that $n$ is prime. For a given base, even though there are infinitely many pseudoprimes to that base, we will see below that below a given threshold and for a given base, most probable primes are primes and only a minuscule fraction of the probable primes are composite.

Take base 2 as an example. Of all the probable primes base 2 that are less than $25 \cdot 10^9$ , how many are primes and how many are composite? According to [2], there are 21853 pseudoprimes base 2 that are less than $25 \cdot 10^9$ . According to the prime number theorem, the number of prime numbers less than $x$ is approximately $\displaystyle x / \text{ln}(x)$ . Therefore there are approximately $1.044 \cdot 10^9$ many primes under $25 \cdot 10^9$ . This example illustrates that most probable primes base 2 under $25 \cdot 10^9$ are primes and that very few of them are pseudoprimes base 2.

Sticking with base 2, the author of [1] showed that the number of pseudoprimes to base 2 under $x$ is less than

$\displaystyle x^{1-w}$

$\displaystyle w=\frac{\text{ln} \ \text{ln} \ \text{ln} x}{2 \text{ln} \ \text{ln} x}$

The above bound on pseudoprimes base 2 grows much slower than the quantity $\displaystyle \frac{x}{\text{ln} x}$ , which is taken as the estimate on the number of primes less than $x$ . This fact suggests that most probable primes are primes.

Thus the result $2^{n-1} \equiv 1 \ (\text{mod} \ n)$ says a lot. It is not a proof that $n$ is prime. But it gives very strong evidence that $n$ is likely a prime, especially if the number $n$ being tested is a randomly chosen number. This strong evidence can be further corroborated by repeating the calculation of the congruence (1) for a large number of bases, preferably randomly chosen. In the experience of the author of this blog, getting $2^{n-1} \equiv 1 \ (\text{mod} \ n)$ is often a turning point in a search for prime numbers. In primality testing of random numbers $n$ , the author has yet come across an instance where $2^{n-1} \equiv 1 \ (\text{mod} \ n)$ is true and the number $n$ turns out to be composite.

___________________________________________________________________

More on pseudoprimes

The Fermat primality test is to use the congruence relation (1) above to check for the primality or the compositeness of a number. If a number is prime, the Fermat test will always detect its primality. For the Fermat test to be a good test, it needs to be able to detect the compositeness of pseudoprimes.

As discussed in the section on “The probabilistic view”, the probable primes to a given base is the union of two disjoint subsets – the primes and the pseudoprimes to that base. The following is another way to state this fact.

$\left\{ \text{probable primes to base } a \right\}=\left\{ \text{primes} \right\} \cup \left\{ \text{pseudoprimes to base } a \right\}$

Furthermore, most of the probable primes below a threshold are primes. Thus if we know that a randomly selected number is a probable prime to a given base, it is likely a prime number.

As discussed above, the composite number 341 is a pseudoprime to base 2 but not to base 3. The integer 2047 is a composite numbers since 23 and 89 are its factors. With $2^{2046} \equiv 1 \ (\text{mod} \ 2047)$ , the number 2047 is a pseudoprime to the base 2. On the hand, $3^{2046} \equiv 1013 \ (\text{mod} \ 2047)$ , the number 2047 is not a pseudoprime to the base 3. For the number 1373653, look at the following three congruences:

$2^{1373652} \equiv 1 \ (\text{mod} \ 1373653)$

$3^{1373652} \equiv 1 \ (\text{mod} \ 1373653)$

$5^{1373652} \equiv 1370338 \ (\text{mod} \ 1373653)$

The above three congruences show that the number 1373653 is a pseudoprime to both bases 2 and 3 but is not a pseudoprime to the base 5. Here’s a larger example. For the number 25326001, look at the following four congruences:

$2^{25326000} \equiv 1 \ (\text{mod} \ 25326001)$

$3^{25326000} \equiv 1 \ (\text{mod} \ 25326001)$

$5^{25326000} \equiv 1 \ (\text{mod} \ 25326001)$

$7^{25326000} \equiv 5872860 \ (\text{mod} \ 25326001)$

The above four congruences show that the number 25326001 is a pseudoprime to bases 2, 3 and 5 but is not a pseudoprime to the base 7.

In primality testing, the pseudoprimes are the trouble makers. These are the composite numbers that exhibits some prime-like quality. So it may be easy to confuse them with prime numbers. The above examples of pseudoprimes (341, 2047, 1373653, 25326001) happen to be not pseudoprimes to some other bases. For this kind of pseudoprimes, the Fermat test will identify them as composite (if the tester is willing to choose enough bases for testing).

What is troubling about the Fermat test is that there are numbers $n$ that are psuedoprimes to all bases that are relatively prime to $n$ . These numbers are called Carmichael numbers. For such numbers, the Fermat test will be wrong virtually 100% of the time!

Consider the number 294409.

$2^{294408} \equiv 1 \ (\text{mod} \ 294409)$

$3^{294408} \equiv 1 \ (\text{mod} \ 294409)$

$4^{294408} \equiv 1 \ (\text{mod} \ 294409)$

$5^{294408} \equiv 1 \ (\text{mod} \ 294409)$

$6^{294408} \equiv 1 \ (\text{mod} \ 294409)$

One might think that the above congruences are strong evidence for primality. In fact, this is a Carmichael number. The factors of 294409 are 37, 73 and 109. The number 294409 is a pseudoprime to all the bases that are relatively prime to 294409. The only way the Fermat test can detect the compositeness of this number is to stumble upon one of its factors. For example, using base 37, we have

$37^{294408} \equiv 143227 \ (\text{mod} \ 294409)$

For a large Carmichael number (say one with hundreds of digits), it will be hard to randomly stumble on a factor. So there will be virtually a 100% chance that the Fermat test will declare a large Carmichael number as prime if the Fermat test is used. Fortunately Carmichael numbers are rare (see here). If the number being tested is randomly chosen, it will not be likely a Carmichael number. So for the most part, the Fermat test will work well. As discussed above, having the congruence relationship (1) for just one base is quite strong evidence for primality.

___________________________________________________________________

Reference

Pomerance C., On the distribution of pseudoprimes, Math. Comp., Volume 37, 587-593, 1981.
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}$

The first prime number after the 8th Fermat number

Posted on November 9, 2014 by Dan Ma

In this post, we discuss a primality testing exercise involving the eighth Fermat number. A Fermat number is of the form $F_n=2^{2^n}+1$ where $n$ is any nonnegative integer. We search for the first prime number that is greater than $F_8$ . The basic idea is to search for the first probable prime base 2 among the odd numbers after $F_8$ . Once the first probable prime base 2 is identified, we apply the Miller-Rabin primality test to confirm that it is a prime number. At the outset of this exercise, we did not know how many numbers we had to check before reaching the first prime number.

The first five Fermat numbers $F_0$ , $F_1$ , $F_2$ , $F_3$ and $F_4$ are the only Fermat numbers that are known to be prime (it was conjectured by Fermat that all Fermat numbers are prime). It is unknown whether there exists prime Fermat number beyond $F_4$ . What is clear, however, is that all the higher Fermat numbers that were studied turn out to be composite. The 8th Fermat number $F_8$ has 78 decimal digits with two factors with 16 and 62 digits (it was factored in 1961). The largest Fermat number that has been completely factored (as of the writing of this post) is $F_{11}$ which has 617 decimal digits. Many Fermat numbers larger than $F_{11}$ have been partially factored.

___________________________________________________________________

The basic approach

The following is the number $2^{256}$ , which has 78 decimal digits.

$2^{256}=$

Define $P_j=2^{256}+j$ where $j$ is an odd positive integer, i.e., $j=1,3,5,7,\cdots$ . The exercise is to find the smallest $j$ such that $P_j$ is a prime number. According to Euclid’s proof that there are infinitely many prime numbers, such a $P_j$ is sure to exist. Just that we do not know at the outset how far we have to go to find it. Of course, $P_1$ is the 8th Fermat number, which is a composite number with two prime factors with 16 and 62 decimal digits. So the search starts with $j=3$ .

The key is to do the following two quick checks to eliminate composite numbers so that we can reach a probable prime as quickly as possible.

For any given $P_j$ , the first step is to look for small prime factors, i.e., to factor $P_j$ using prime numbers less than a bound $B$ . If a small prime factor is found, then we increase $j$ by 2 and start over. Note that we skip any $P_j$ where the sum of digits is divisible by 3. We also skip any $P_j$ that ends with the digit 5.
If no small factors are found, then compute the congruence $2^{P_j-1} \ (\text{mod} \ P_j)$ . If the answer is not congruent to 1, then we know $P_j$ is composite and work on the next number. If $2^{P_j-1} \equiv 1 \ (\text{mod} \ P_j)$ , then $P_j$ is said to be a probable prime base 2. Once we know that a particular $P_j$ is a probable prime base 2, it is likely a prime number. To further confirm, we apply the Miller-Rabin primality test on that $P_j$ .

In the first check, we check for prime factors among the first 100 odd prime numbers (i.e. all odd primes up to and including 547).

___________________________________________________________________

Searching the first probable prime

At the outset, we did not know how many numbers we will have to check. Since there can be a long gap between two successive prime numbers, the worse fear is that the number range we are dealing with is situated in such a long gap, in which case we may have to check thousands of numbers (or even tens of thousands). Luckily the search settles on a probable prime rather quickly. The magic number is 297. In other words, for the number

$P_{297}=2^{256}+297$

, we find that $2^{P_{297}-1} \equiv 1 \ (\text{mod} \ P_{297})$ . Thus $P_{297}$ is a probable prime in base 2. The following shows the decimal digits of $P_{297}$ .

$P_{297}=$

To further give a sense of how the magic number $P_{297}$ is reached, the following table lists the 25 calculations leading to the magic number.

$\left[\begin{array}{rrrrrrr} j & \text{ } & \text{last 5 digits of } P_j & \text{ } & \text{least factor of } P_j & \text{ } & 2^{P_j-1} \ \text{mod} \ P_j \\ \text{ } & \text{ } & \text{ } \\ 259 & \text{ } & 40195 & \text{ } & 5 & \text{ } & \text{ } \\ 261 & \text{ } & 40197 & \text{ } & * & \text{ } & \not \equiv 1 \\ 263 & \text{ } & 40199 & \text{ } & 3 & \text{ } & \text{ } \\ 265 & \text{ } & 40201 & \text{ } & * & \text{ } & \not \equiv 1 \\ 267 & \text{ } & 40203 & \text{ } & * & \text{ } & \not \equiv 1 \\ 269 & \text{ } & 40205 & \text{ } & 3 & \text{ } & \text{ } \\ 271 & \text{ } & 40207 & \text{ } & 7 & \text{ } & \text{ } \\ 273 & \text{ } & 40209 & \text{ } & * & \text{ } & \not \equiv 1 \\ 275 & \text{ } & 40211 & \text{ } & 3 & \text{ } & \text{ } \\ 277 & \text{ } & 40213 & \text{ } & 11 & \text{ } & \text{ } \\ 279 & \text{ } & 40215 & \text{ } & 5 & \text{ } & \text{ } \\ 281 & \text{ } & 40217 & \text{ } & 3 & \text{ } & \text{ } \\ 283 & \text{ } & 40219 & \text{ } & 13 & \text{ } & \text{ } \\ 285 & \text{ } & 40221 & \text{ } & 7 & \text{ } & \text{ } \\ 287 & \text{ } & 40223 & \text{ } & 3 & \text{ } & \text{ } \\ 289 & \text{ } & 40225 & \text{ } & 5 & \text{ } & \text{ } \\ 291 & \text{ } & 40227 & \text{ } & 23 & \text{ } & \text{ } \\ 293 & \text{ } & 40229 & \text{ } & 3 & \text{ } & \text{ } \\ 295 & \text{ } & 40231 & \text{ } & 71 & \text{ } & \text{ } \\ 297 & \text{ } & 40233 & \text{ } & * & \text{ } & \equiv 1 \end{array}\right]$

The first number is in the table $P_{259}$ ends in a 5 and is thus composite. The third number $P_{263}$ is composite since the sum of the digits of its is divisible by 3. The third column of the above table shows the least prime factor below 547 (if one is found). An asterisk in the third column means that none of the prime numbers below 547 is a factor. For such numbers, we compute the modular exponentiation $2^{P_j-1} \ (\text{mod} \ P_j)$ .

In the above table, 4 of the asterisks lead to the result $2^{P_j-1} \not \equiv 1 \ (\text{mod} \ P_j)$ . These numbers $P_j$ are thus composite. For example, for $P_{273}$ , the following is the result:

$2^{P_{273}-1} \ (\text{mod} \ P_{273}) \equiv$

The last number $P_{297}$ in the table is a probable prime base 2 since our calculation shows that $2^{P_{297}-1} \equiv 1 \ (\text{mod} \ P_{297})$ . Being a probable prime to base 2 is actually very strong evidence that the number is a prime number. We want even stronger evidence that $P_{297}$ is a prime. For example, we can carry out the Miller-Rabin test in such a way that the probability of mistaking a composite number as prime is at most one in a septillion! A septillion is the square of a trillion. A trillion is $10^{12}$ . Thus a septillion is $10^{24}$ . One in a septillion is for all practical purposes zero. But if one wants more reassurance, one can always run the Miller-Rabin test with more bases.

___________________________________________________________________

The Miller-Rabin primality test

The Miller-Rabin test is a variant of the Fermat test because Miller-Rabin still relies on Fermat’s little theorem. But Miller-Rabin uses Fermat’s little theorem in such a way that it eliminates the issue of the Fermat test mistakenly identifying Carmichael numbers as prime.

Given an odd positive integer whose “prime or composite” status is not known, the Miller-Rabin test will output “composite” or “probable prime”. Like the Fermat test, the Miller-Rabin test calculates $a^{n-1} \ (\text{mod} \ n)$ for several values of $a$ . But the test organizes the congruence $a^{n-1} \ (\text{mod} \ n)$ a little differently to capture additional information about prime numbers.

Here’s how to set up the calculation for Miller-Rabin. Because $n$ is odd, $n-1$ is even. We can factor $n-1$ as a product of a power of 2 and an odd number. So we have $n-1=2^k \cdot q$ where $k \ge 1$ and $q$ is odd ( $q$ may not be prime). Then we calculate 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} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The first term in (1) can be calculated using the fast powering algorithm (using the binary expansion of $q$ to convert the calculation of $a^q$ into a series of squarings and multiplications). Each subsequent term is then the square of the preceding term. The last term is of course $a^{n-1}$ . Each squaring or multiplication is reduced modulo $n$ . The Miller-Rabin test is based on the following property of prime numbers:

Theorem 1

$n$

$n-1=2^k \cdot q$

$k \ge 1$

$q$

$a$

$n$

At least one term in the sequence (1) is congruent to 1 modulo $n$ .
Either the first term in (1) is congruent to 1 modulo $n$ or the term preceding the first 1 is congruent to -1 modulo $n$ .

How the Miller-Rabin test works
Suppose that the “prime or composite” status of an odd integer $n$ is not known. If both conditions in the above theorem are satisfied with respect to the number $a$ , then $n$ is said to be a strong probable prime in base $a$ . If a strong probable prime in base $a$ happens to be composite, then it is said to be a strong pseudoprime in base $a$ . In other words, a strong pseudoprime is a composite number that possesses a prime-like property, namely it satisfies the two conditions in Theorem 1 with respect to one base $a$ .

The test procedure of Miller-Rabin is to check whether $n$ is a strong probable prime to several bases that are randomly chosen. The following determines the outcome of the test:

If $n$ is not a strong probable prime in one of the chosen bases, then $n$ is proved to be composite.
If $n$ is shown to be a strong probable prime in all the chosen bases (say there are $k$ of them), then $n$ is “probably prime” with an error probability of at most $0.25^k$ .

To prove the integer $n$ is composite, we look for a base $a$ for which $n$ is not a strong probable prime. Such a value of $a$ is also called a Miller-Rabin witness for the compositeness of $n$ . For primality, the Miller-Rabin test does not give a mathematical proof that a number is prime. The Miller-Rabin test is a probable prime test. It gives strong evidence that $n$ is a prime number, with an error probability that can be made arbitrarily small by using a large random sample of values of $a$ .

Take the prime candidate $P_{297}$ that is discussed above. We plan to run the Miller-Rabin test on $P_{297}$ using 40 random values of $a$ where $1<a<P_{297}$ . If $P_{297}$ is shown to be a strong probable prime in all 40 bases, then the prime candidate $P_{297}$ is likely a prime number with an error probability of at most $0.25^{40}$ . This probability works out to be less than 1 in 10 raised to 24 (hence the one in a septillion that is mentioned earlier). If one wants stronger evidence, we can compute for more values of $a$ . Thus if $P_{297}$ is in actuality a composite number, there is at most a one in septillion chance that the Miller-Rabin test will declare $P_{297}$ is a prime number.

How can the Miller-Rabin test make the claim of having such a small error probability? The fact the the error probability of Miller-Rabin can be made arbitrarily small stems from the following fact.

Theorem 2

$n$

$1<a<n$

$n$

$1<a<n$

$n$

To paraphrase Theorem 2, if $n$ is composite to begin with, at least 75% of the numbers in $1<a<n$ will prove its compositeness. That means that at most 25% of the numbers $a$ will exhibit the prime-like property described in Theorem 1. The power of Miller-Rabin comes from the fact that for composite numbers there are more values of $a$ that will give a correct result (in fact, at least 3 times more).

Thus if you apply the Miller-Rabin test on a composite number $n$ , you will bound to stumble on a base $a$ that will prove its compositeness, especially if the bases are randomly chosen. Any random choice of $a$ where $1<a<n$ has at least a 75% chance of being correct on the composite number $n$ . In a series of 100 random choices of $a$ , it will be hard to miss such values of $a$ . The only way that Miller-Rabin can make a mistake by declaring a composite number as prime is to pick all the values of $a$ from the (at most) 25% of the pool of values of $a$ that are strong pseudoprime prime. This probability is bounded by $0.25^k$ (if $k$ is the number of selections of $a$ ).

___________________________________________________________________

Applying Miller-Rabin on the prime candidate

The first task is to factor $P_{297}-1$ . We find that $P_{297}-1=2^3 \times q$ where $q$ is the following odd number:

$q=$

For each randomly selected $a$ , we calculate the following sequence:

$a^q, \ a^{2q}, \ a^{4q}, \ a^{8q} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

The first term is calculated using the fast powering algorithm (a series of squarings and multiplications). Each subsequent term is the square of the preceding term. Each term in the sequence is reduced modulo $P_{297}$ . The goal is to see if the two conditions in Theorem 1 are satisfied. One is that one of the 4 values in (2) is a 1. The other is that the term preceding the first 1 in (2) has to be a -1.

The following shows the 40 numbers that are randomly chosen in the interval $1<a<P_{297}$ .

$a_1=$
03006957708701194503849170682264647623506815369915
7798209693214442533348380872
$a_2=$
02223067440101780765895379553626469438082041828085
0568523022714143509352911267
$a_3=$
04531895131849504635258523281146698909008537921009
6337435091877410129499153591
$a_4=$
05434508269932993379745836263818598804800824522102
0278113825689716192402178622
$a_5=$
08799241442673378780142202326330306495270149563840
3866810486309815815031353521
$a_6=$
02638607393577034288802880492058261281940769238659
8928068666401909247319838064
$a_7=$
04283430251977183138176255955338099404217762991191
9192783003754562986178981473
$a_8=$
09773398144692973692102006868849010147546139698798
3443958657834362269077067224
$a_9=$
05504666974469005713839308880951115507992521746498
7157086751623602877205126361
$a_{10}=$
11369425784373951812019794994427515082375862595853
6524984616385315102874812557
$a_{11}=$
11280428157869817083329641054154150272024966029283
2165114734540900026838117128
$a_{12}=$
11208322317253928483879618989535357346499197200982
7728283667193655956607063861
$a_{13}=$
05585951853297694372636067012444311272073854408338
4421611399136081624631900538
$a_{14}=$
06831924581003106427566658433259804779354874917795
9811865334330929987281859876
$a_{15}=$
07339174229323952008915772840377019251465052264221
1294344032116313026124007734
$a_{16}=$
05117387267263929174559713098463717229625661656017
7194611080485470890280573816
$a_{17}=$
06599941646668915168578091934085890873056463577356
8090503454939353325803291530
$a_{18}=$
07545265152740184887140788322673806569482388835389
5577110370797470603035554930
$a_{19}=$
02591621894664804222839429868664505564743756550515
2520842332602724614579447809
$a_{20}=$
04791002227899384351266879075743764807247161403811
8767378458621521760044966007
$a_{21}=$
03251071871924939761772100645669847224066002842238
6690935371046248267119967874
$a_{22}=$
07211128555514235391448579740428274673170438137060
9390617781010839144521896079
$a_{23}=$
02839820419745979344283855308465698534375525126267
1701870835230228506944995955
$a_{24}=$
06304631891686637702274634195264042846471748931602
4893381338158934204519928855
$a_{25}=$
06492095235781034422561843267711627481401158404402
2978856782776323231230432687
$a_{26}=$
11078868891712009912929762366314190797941038596568
5459274315695355251764942151
$a_{27}=$
05795069944009506186885816367149671702413127414386
2708093175566185349033983346
$a_{28}=$
01712922833914010148104423892201355622294341143990
7524285008693345292476544524
$a_{29}=$
09743541325262594740093734822046739122734773994479
9814337973200740861495044676
$a_{30}=$
02503872375817370838455279068302037475992008315394
2976462871038003917493744995
$a_{31}=$
06980677383898331402575574511880992071872803011356
6498794763450065008785347168
$a_{32}=$
01507075889390134242331585173319278262699562685820
7121480322563439665642035394
$a_{33}=$
02471785068822350832987019936892052187736451275830
5372059292781558599916131031
$a_{34}=$
10950891460180297156465120507537244257810396062906
9207306297501015755045004254
$a_{35}=$
11052976297188507170707306917942099264941855478856
2965936913589165233381674539
$a_{36}=$
03911878231948499128291863266472008604449261315172
1053813631612297577166335941
$a_{37}=$
06903294587603383022211116535092146484651980588002
9291840261276683214113088012
$a_{38}=$
03942020579038616658412018517396703874933208670283
3087287933190554281896471934
$a_{39}=$
04338728160253711124705740270085271024911573570055
1690460857511205663297661796
$a_{40}=$
06707597137792150532106913489524457238449067437061
7211249957355483821516113140

For each random number $a_j$ , we calculated the 4 numbers indicated in sequence (2). The following 3 tables show the results of the calculation.

$\left[\begin{array}{rrrrrrrrr} j & \text{ } & a_j^q & \text{ } & a_j^{2q} & \text{ } & a_j^{4q} & \text{ } & a_j^{8q} \\ \text{ } & \text{ } & \text{ } \\ 1 & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \\ 2 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 3 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 4 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 5 & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 6 & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \\ 7 & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \\ 8 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 9 & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \\ 10 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 11 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 12 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 13 & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 14 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 15 & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \end{array}\right]$

$\left[\begin{array}{rrrrrrrrr} j & \text{ } & a_j^q & \text{ } & a_j^{2q} & \text{ } & a_j^{4q} & \text{ } & a_j^{8q} \\ \text{ } & \text{ } & \text{ } \\ 16 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 17 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 18 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 19 & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \\ 20 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 21 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 22 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 23 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 24 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 25 & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 & \text{ } & 1 \\ 26 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 27 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 28 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 29 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 30 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \end{array}\right]$

$\left[\begin{array}{rrrrrrrrr} j & \text{ } & a_j^q & \text{ } & a_j^{2q} & \text{ } & a_j^{4q} & \text{ } & a_j^{8q} \\ \text{ } & \text{ } & \text{ } \\ 31 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 32 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 33 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 34 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 35 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 36 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 37 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 38 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \\ 39 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1 \\ 40 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & -1 & \text{ } & 1 \end{array}\right]$

There are 4 columns of calculation results, one for each term in sequence (2). If a calculation result is a blank in the above tables, it means that the result is a number that is not 1 or -1 modulo $P_{297}$ . For example, $a_1^q \ (\text{mod} \ P_{297})$ and $a_2^q \ (\text{mod} \ P_{297})$ are congruent to the following two numbers:

$a_1^q \equiv$

$a_2^q \equiv$
10235477176842589582260882228891913141693105976929
7597880545619812030150151760

In the above 3 tables, all results match the conditions of Theorem 1. For each number $a_j$ , the calculated results are eventually 1. On some of the rows, the first result is a 1. In all the other rows, the term right before the first 1 is a -1. For example, in the first row where $j=1$ , the first 1 $a_1^{4q}$ and the term preceding that is a -1.

The results in the above 3 tables show that the number $P_{297}$ is a strong probable prime in all 40 of the randomly chosen bases. We have very strong evidence that the number $P_{297}$ is a prime number. The probability that it is a composite number but we mistakenly identify it as prime is at most one in a septillion!

___________________________________________________________________

Exercise

In our search for probable primes larger than the 8th Fermat number, we also find that the number $P_{301}=2^{301}+301$ is also a probable prime base 2. The following shows the decimal digits:

$P_{301}=$

Is it a prime number? Perform the Miller-Rabin test on this number.

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

A primality testing exercise from RSA-100

Posted on October 20, 2014 by Dan Ma

In this post, we work on a primality testing exercise obtained by altering one digit of a known large prime number. The idea is that we take a known large prime number, change one of the digits and test the primality of the resulting number. In this post, we use the smaller prime factor of the number that is known as RSA-100. The goal is to keep changing digits (one at a time) until we obtain a prime number.

RSA-100 is the smallest RSA number. It is a 330-bit number (has 100 decimal digits). It was factored in 1991. The following are RSA-100 and its two factors.

RSA-100

Prime Factors of RSA-100
$p=$ 37975227936943673922808872755445627854565536638199
$q=$ 40094690950920881030683735292761468389214899724061

The exercise is to alter one digit of the smaller factor $p$ until we get a prime number. Each position of $p$ can be altered in 9 different ways. For example, the leading digit of $p$ can be changed to 0,1,2,4,5,6,7,8,9. The leading digit being changed to 0 has the effect that the leading digit is truncated (the resulting number is a 49-digit number).

___________________________________________________________________

The approach we take

Our approach is to work on one digit (position) of $p$ at a time. Once we pick a position, we examine the 9 different resulting numbers. For each of the 9 numbers, we perform the following three quick checks for compositeness.

Check the sum of the digits. If the sum is divisible by 3, then the number is divisible by 3.
Look for small prime factors.
If $n$ is the number being tested, calculate $2^{n-1} \ (\text{mod} \ n)$ . If it is not congruent to 1, we know $n$ is composite.

If any one of the checks turns up composite, we move on to another one of the 9 numbers. If all three checks fail to turn up composite, then we perform the Fermat primality test on that number. On the other hand, if all 9 numbers are found to be composite by the quick checks, then we pick another position and perform the same procedure.

___________________________________________________________________

The connection with weakly prime numbers

It is not entirely clear that the exercise of altering one digit of the smaller factor of RSA-100 will eventually produce a prime number. In fact, there are prime numbers such that altering one digit will always produce a composite number. Such prime numbers are called weakly prime numbers. So the exercise we propose is to find out whether $p$ , the smaller factor of RSA-100, is a weakly prime number. Our hope is that $p$ is not weakly prime. If one is patient and has a calculator that can work with large numbers, the answer will eventually be found. The number $p$ has 50 digits. So there are 450 numbers to check. However, we hope that a prime number will emerge long before having to check the 450th number.

The first few weakly prime numbers are 294001, 505447, 584141, 604171, 971767, 1062599.

___________________________________________________________________

The first iteration

Our first iteration is on altering the first digit (the leading digit) of $p$ . We have the following 9 numbers as a result.

$A_0=$

$A_1=$

$A_2=$

$A_4=$

$A_5=$

$A_6=$

$A_7=$

$A_8=$

$A_9=$

The first check shows that $A_1$ , $A_4$ and $A_7$ are divisible by 3. Their sums of digits are 264, 267 and 270, respectively. We can rule out these three numbers. We then divide each remaining number by primes up to (and including) 97. We find that $A_0$ , $A_2$ and $A_9$ have small factors. Here are their factors:

$A_0$

$A_2$

$A_9$

The remaining numbers are $A_5$ , $A_6$ and $A_8$ . We then compute the modular exponentiation in the third check. Here are the results:

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

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

$2^{A_8-1} \equiv w \ (\text{mod} \ A_8)$

where

$u=$

$v=$

$w=$

Clearly $u,v,w$ are not 1. Thus $A_5$ , $A_6$ and $A_8$ are all composite. The first iteration yields no prime number.

___________________________________________________________________

Another 2 iterations

Next we choose to alter the second digit (the digit right after the leading digit). By applying the same procedure as for the first iteration, we find that all 9 resulting numbers are composite.

Unwilling to go with the natural order (3rd position, 4th position and so on), we choose the 27th position as the next iteration, 27th counting from the leading digit of $p$ . The following are the resulting 9 numbers:

$B_0=$

$B_1=$

$B_2=$

$B_3=$

$B_4=$

$B_5=$

$B_6=$

$B_8=$

$B_9=$

The first check shows that $B_2$ , $B_5$ and $B_8$ are divisible by 3. Their sums of digits are 261, 264 and 267, respectively. These 3 numbers $B_2$ , $B_5$ and $B_8$ are out. Now look for small factors in the remaining numbers. Divide each of the remaining numbers by small primes up to (and including) 97. Small factors are found for three of them. They are:

$B_0$

$B_3$

$B_6$

The remaining numbers are $B_1$ , $B_4$ and $B_9$ . We then compute the modular exponentiation in the third check. Here are the results:

$2^{B_1-1} \equiv f \ (\text{mod} \ B_1)$

$2^{B_4-1} \equiv g \ (\text{mod} \ B_4)$

$2^{B_9-1} \equiv h \ (\text{mod} \ B_9)$

where

$f=$

$g=$

$h=$

We have some interesting results by going to the 27th position. We have two numbers $B_1$ and $B_9$ that pass the three quick checks. These two numbers could still be composite. It could be that they have large factors that we have not detected. Or they have slightly larger Fermat witnesses that we have not yet found. We hope to settle these issues by applying a more formal primality test.

___________________________________________________________________

Checking for more evidence of primality

We wish perform primality testing on the number $B_1$ , the result of altering the 27th digit of the smaller factor of RSA-100 to the digit of 1.

$B_1=$ 37975227936943673922808872155445627854565536638199

Before starting the Fermat test, we want to get further indication that $B_1$ is a prime. A quick check is to calculate $a^{B_1-1} \ (\text{mod} \ B_1)$ for a few more small values of $a$ . In addition to $a=2$ that is done earlier, we have the following results:

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

$3^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

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

$7^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

$11^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

$13^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

$17^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

$19^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

$23^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

$29^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

So far so good. The Fermat congruence $a^{B_1-1} \ (\text{mod} \ B_1)$ for the first 10 prime numbers $a$ indicates that $B_1$ may be a prime number. Some authors would stop at this point and declare that the number $B_1$ is prime. However, to minimize the chance of making a mistake (incorrectly identifying a composite number as prime), the values of $a$ should not be predetermined and should instead be randomized.

In any case, all the initial checks turn up no evidences that rule out primality for the number $B_1$ . We now continue with a randomized implementation of the Fermat test.

___________________________________________________________________

Fermat primality test

The Fermat test works the same as in the previous section, namely to calculate $a^{B_1-1} \ (\text{mod} \ B_1)$ for more values of $a$ , except that the values $a$ are randomly selected. The following are 20 randomly selected values of $a$ where $1<a<B_1$ .

$a_1=$

$a_2=$

$a_3=$

$a_4=$

$a_5=$

$a_6=$

$a_7=$

$a_8=$

$a_9=$

$a_{10}=$

$a_{11}=$

$a_{12}=$

$a_{13}=$

$a_{14}=$

$a_{15}=$

$a_{16}=$

$a_{17}=$

$a_{18}=$

$a_{19}=$

$a_{20}=$

To use the Fermat’s little theorem, we need to check that each one of these values of $a$ is relatively prime to the modulus $B_1$ . We use the Euclidean algorithm to compute $\text{GCD}(a_j,B_1)$ for all $j=1,2,\cdots,20$ . The results are:

$\text{GCD}(a_1,B_1)=1$

$\text{GCD}(a_2,B_1)=1$

$\text{GCD}(a_3,B_1)=1$

$\text{GCD}(a_4,B_1)=1$

$\text{GCD}(a_5,B_1)=1$

$\text{GCD}(a_6,B_1)=1$

$\text{GCD}(a_7,B_1)=1$

$\text{GCD}(a_8,B_1)=1$

$\text{GCD}(a_9,B_1)=1$

$\text{GCD}(a_{10},B_1)=1$

$\text{GCD}(a_{11},B_1)=1$

$\text{GCD}(a_{12},B_1)=1$

$\text{GCD}(a_{13},B_1)=1$

$\text{GCD}(a_{14},B_1)=1$

$\text{GCD}(a_{15},B_1)=1$

$\text{GCD}(a_{16},B_1)=1$

$\text{GCD}(a_{17},B_1)=1$

$\text{GCD}(a_{18},B_1)=1$

$\text{GCD}(a_{19},B_1)=1$

$\text{GCD}(a_{20},B_1)=1$

Each random number is relatively prime to the number $B_1$ . This provides another check. If any of the GCD is greater than 1, then we would have found divisor of $B_1$ that is greater than 1, in which case the primality test will be aborted.

Now we proceed to calculate $a_j^{B_1-1} \ (\text{mod} \ B_1)$ . If any one of these congruence values is not 1, then we declare that $B_1$ is composite. If all 20 congruence values are 1, then we declare that $B_1$ is a prime number. The following table shows the results.

$\left[\begin{array}{rrr} a_j & \text{ } & a_j^{B_1-1} \ \text{mod} \ B_1 \\ \text{ } & \text{ } & \text{ } \\ a_1 & \text{ } & 1 \\ a_2 & \text{ } & 1 \\ a_3 & \text{ } & 1 \\ a_4 & \text{ } & 1 \\ a_5 & \text{ } & 1 \\ a_6 & \text{ } & 1 \\ a_7 & \text{ } & 1 \\ a_8 & \text{ } & 1 \\ a_9 & \text{ } & 1 \\ a_{10} & \text{ } & 1 \\ a_{11} & \text{ } & 1 \\ a_{12} & \text{ } & 1 \\ a_{13} & \text{ } & 1 \\ a_{14} & \text{ } & 1 \\ a_{15} & \text{ } & 1 \\ a_{16} & \text{ } & 1 \\ a_{17} & \text{ } & 1 \\ a_{18} & \text{ } & 1 \\ a_{19} & \text{ } & 1 \\ a_{20} & \text{ } & 1 \end{array}\right]$

The Fermat test results, both the predetermined part with the first 10 prime numbers and the randomized part with the 20 random selections, show that we have very strong evidence that the number $B_1$ is a prime number. All together, we have shown that $a^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$ for 30 values of $a$ , 20 of which are randomly selected in the interval $1<a<B_1$ .

Recall Fermat's little theorem, which states that if $n$ is a prime number, then $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for all integers $a$ relatively prime to the modulus $n$ .

With $a^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$ being true for 30 values of $a$ relatively prime to $B_1$ , if we declare that $B_1$ is prime, what is the probability of making a mistake? Put another way, if $B_1$ is really a composite number, what is the probability of getting $a^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$ for 20 random choices of $a$ ? The probability is practically zero, except for one caveat. Thus we declare that $B_1$ is a prime number with the one caveat discussed below.

___________________________________________________________________

Remarks

There are composite integers $n$ such that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for every integer $a$ that is relatively prime to $n$ . These composite integers are called Carmichael numbers. The smallest Carmichael number is 561 (with factors 3, 11, 17).

The Fermat test will always declare a Carmichael number as prime. In other words, the Fermat test will always give a false positive if the test is applied on a Carmichael number. Fortunately Carmichael numbers are rare. So when the number whose primality is being tested is randomly selected, the Fermat test will often give the correct result. Selecting a number at random, it is not likely to pick a Carmichael number. But the number $B_1$ is not obtained by random selection. It is obtained in a predetermined way (by altering one digit of a known prime number).

So if you have a nagging worry that the number $B_1$ might be a Carmichael number, the Miller-Rabin test should be used instead. Carmichael numbers will not evade the Miller-Rabin test. When applying the Miller-Rabin test on a composite number (Carmichael number or not), it will detect the compositeness with arbitrarily small error probability.

The Miller-Rabin test is an extension of the Fermat test and has minimal additional calculation. We actually structure the calculation of $a_j^{B_1-1} \ (\text{mod} \ B_1)$ in the above table with the Miller-Rabin test in mind. We find that the Miller-Rabin test also indicates that the number $B_1$ is prime. With the 20 random values of $a$ , the error probability is at most $0.25^{20}$ , which is for all practical purposes zero. In other words, if $B_1$ were a composite number, there would be a close to zero chance that Miller-Rabin test would make a mistake by declaring $B_1$ a prime number. With such a small error probability, we declare that the number $B_1$ is prime.

Tying back to the notion of weakly prime numbers, we have found a prime number by altering one digit of the prime number $p$ , the smaller factor of RSA-100. Thus the prime number $p$ is not a weakly prime number.

___________________________________________________________________

Exercises

The number

$B_9=$ 37975227936943673922808872955445627854565536638199

,obtained by changing the 27th digit of the smaller factor $p$ of RSA-100 to the digit of 9, is a probable prime (see above). Test the primality of this number.

Find another prime number by altering a different digit of $p$ .

Another possible exercise is to do the same exercise on the larger factor of RSA-100 or factors of other RSA numbers.

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

A primality testing exercise from the 9th Fermat number

Posted on October 18, 2014 by Dan Ma

In this post, we discuss a primality testing exercise on a number derived from a prime factor of the 9th Fermat number. The idea of the exercise is that we test the primality of a number generated from a known large prime number by tagging or inserting a digit into the known prime number. This is an excellent way to generate exercises for primality testing. This approach of altering a known prime number is not meant to be a prime number generation process.

A Fermat number is a positive integer of the form $F_n=2^{2^n}+1$ where $n=0,1,2,\cdots$ . The 9th Fermat number is $F_9=2^{2^9}+1=2^{512}+1$ . This is a 155-digit number that was completely factored in 1993 [1]. Its three prime factors have 7 digits, 49 digits and 99 digits. The following is the 49-digit factor of $F_9$ :

The above 49-digit number is a prime number that was resulted from a published effort of factorizing $F_9$ . The other two factors of $F_9$ can be found in [1] or here. If we tag a digit in front of this 49-digit number, say the digit 6, is the resulting number a prime number? In this post, we discuss the primality testing of the following 50-digit number:

$A=$

Primality testing is an important aspect of public key cryptography. For example, the modulus in the public key in RSA cryptosystem is a product of two distinct large prime numbers. To generate the key, it is crucial to generate large numbers at random and to be able to efficiently test whether the numbers are prime.

___________________________________________________________________

Pre-checks before primality testing

Primality tests such as Fermat test and Miller-Rabin test are popular and are easy to use. These tests check for the primality of a given integer $n$ by randomly choosing a set of auxiliary numbers and then checking whether any one of these auxiliary values is a witness to the compositeness of the number $n$ . We would like to emphasize the point that before applying a randomized primality testing procedure, it will be advantageous to perform some easy checks to quickly rule out primality. If these quick checks show that the number being tested is composite, we can then continue the search by moving on to another candidate prime number. With the above number $A$ as example, we perform the following pre-checks.

Check small prime numbers just in case the number being tested has small prime factors.
If the previous step produces no factors, look for small Fermat witnesses.

The idea of the first check is clear. A Fermat witness for an integer $n$ is an integer $a$ that is relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ . If we can find such a number $a$ , we can say conclusively that $n$ is not a prime number. According to Fermat’s little theorem, if $n$ is a prime number, then the congruence would be a one, i.e., $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ . This idea is the basis for the Fermat primality test, which is performed on a random set of values of $a$ . Here in the pre-check, we calculate $a^{n-1} \ (\text{mod} \ n)$ for some small values of $a$ such as 2 or 3. The idea is to quickly rule out the candidate prime numbers that happen to have a small Fermat witness.

If either one of the two checks indicate the number being tested is composite, then we pick another number to test. If both of the above steps fail to indicate compositeness, we can then proceed to use the “probabilistic” part of the Fermat test or another probabilistic primality test.

We like to point out that at the outset, the author of the blog did not know the primality status of the 50-digit number $A$ that is obtained by tagging a 6 in front of the 49-digit factor of the 9th Fermat number. Though this number is far too small to work in the RSA algorithm, it serves as an excellent exercise for primality testing.

___________________________________________________________________

Pre-checking the number $A$

Very quickly, 7 is found to be a factor of $A$ . We have $A=7 \times B$ where $B$ is:

$B=$

We then try to find small factors of $B$ . The number 283 is found to be a factor of $B$ . Then we have $A=7 \times 283 \times C$ where $C$ is the following 47-digit number:

$C=$

By tagging a 6 in front of the 49-digit factor of the 9th Fermat number, we obtain a composite number. The prime or composite status for the number $A$ is settled. Now the next question: is the remaining factor $C$ prime or composite?

___________________________________________________________________

Pre-checking the number $C$

We perform the two pre-checks as described above. In searching for small factors, we find that $C$ is not divisible by all prime numbers less than 200,000. So if $C$ has a factor, it will have to be a large one. Or it could be that $C$ is prime. Instead of continuing to search for factors, we can do the second check. We calculate $2^{C-1} \ (\text{mod} \ C)$ and find that:

$2^{C-1} \equiv t \ (\text{mod} \ C)$

where $t=$ 7426390354305013563302537374271875139618265902

Since $t$ clearly is not 1, this tells us that $C$ is composite.

___________________________________________________________________

Remarks

Instead of doing the randomized primality testing right away, it makes sense to do the pre-checks as described above so that we do not waste time and effort on composite numbers that have small factors or have small Fermat witnesses. As soon as these two checks indicate the compositeness of a number, we then move on to another candidate prime number. If a number passes these two checks, then we can apply a primality test such as the Fermat test or the Miller-Rabin test.

Another remark is that primality testing is easy while factoring is hard. The compositeness of the 47-digit number $C$ can be determined by just one modular exponentiation calculation, which can be computed using the fast powering algorithm. This algorithm uses the binary expansion of the exponent to convert the modular exponentiation into a series of squarings and multiplications. Because the exponent $C-1$ is a 155-bit number, computing $2^{C-1} \ (\text{mod} \ C)$ only requires 154 squarings and at most 154 multiplications (the actual count of multiplications is 76). Implemented in a modern computer, this calculation takes less than one second.

On the other hand, factoring the above 47-digit number $C$ by the brute force approach (checking every possible prime factor) would require checking approximately $2 \times 10^{20}$ many prime numbers as potential factors. The age of the universe is believed to be about 13 billions years, which is about $4 \times 10^{17}$ seconds. That’s why we stop checking for prime factors of $C$ at some point. The authors of [1] factored a 155-digit number in 1993. So the current computing technology is certainly capable of factoring a 47-digit number. But the effort will take time and will require using more advanced factoring algorithm.

___________________________________________________________________

Exercises

The idea of the exercise is that we test the primality of a number generated from a known large prime number by tagging or inserting a digit into the known prime number. Using the same 49-digit factor of $F_9$ , we can tag another digit in front or insert a digit somewhere in the middle. Another possibility is to try the other two factors of $F_9$ .

There are many other large primes to be found on the Internet that can be used for this exercise. For example, factors of other Fermat numbers and RSA numbers.

___________________________________________________________________

Reference

Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M. The Factorization of the Ninth Fermat Number, Mathematiics of Computation, Volume 61, Number 203, July 1993, Pages 319-349.

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

Mathematical Cryptography

focusing on the math in public key cryptography

Tag Archives: Primality testing

Strong probable primes and strong pseudoprimes

The Fermat primality test

Probable primes and pseudoprimes

The first prime number after the 8th Fermat number

A primality testing exercise from RSA-100

A primality testing exercise from the 9th Fermat number