A primality proving algorithm using a theorem of Lucas

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

___________________________________________________________________

The theorem

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

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

The function \phi is Euler’s phi function. If n is a prime number, \phi(n)=n-1. The following lemma shows that the converse is true. The lemma is used in proving Theorem 1.

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

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

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

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

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

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

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

___________________________________________________________________

The primality test from the theorem

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

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

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

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

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

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

___________________________________________________________________

Examples

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

Example 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Example 2

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

    n= 3825123056546413183.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Example 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

We generate the following 8 random choices of a

    013397886753078290
    193080712858269996
    012695419760523254
    096180046746919966
    134541150430885987
    212892893489065625
    209448807773524821
    141141720485036352

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

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

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

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

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

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

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

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

___________________________________________________________________

Exercises

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

    204482919124364689
    3825123056546413093
    3825123056546413133
    3825123056546413211
    3825123056546413213

___________________________________________________________________

Reference

  1. Lehmer D. H., Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc., 33, 327-340 1927.

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

Large Carmichael numbers that are strong pseudoprimes to several bases

There is a very strong theorem in the paper [1] that has impactful theoretical results. For example, Theorem 1 in [1] implies that for any given finite set of bases, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the bases in the given finite set. Another implication of Theorem 1 of [1] is that there are infinitely many Carmichael numbers that have no small prime factors.

Given an odd number n whose “prime versus composite” status is not known, set n-1=2^k \cdot Q where k \ge 1 and Q is odd. The number n is said to be a probable prime to base a if the conclusion of Fermat’s little theorem holds, i.e., a^{n-1} \equiv 1 \ (\text{mod} \ n). A probable prime to base a could be prime or could be composite. If the latter, it is said to be a pseudoprime to base a.

The number n is said to be a strong probable prime to base a if a^{Q} \equiv 1 \ (\text{mod} \ n) or there exists some j=0,1,2,\cdots,k-1 such that a^{2^j \cdot Q} \equiv -1 \ (\text{mod} \ n). In other words, the number n is a strong probable prime to base a if in the following sequence

    a^Q, \ a^{2 \cdot Q}, \ a^{2^2 \cdot Q}, \cdots, \ a^{2^{k-1} \cdot Q}, a^{2^k \cdot Q} \ \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

the first term is a 1 or there exists a -1 followed by a 1. A strong probable prime to base a could be prime or could be composite. If the latter, it is said to be a strong pseudoprime to base a.

According to [6], there are only 4842 strong pseudoprimes to base 2 below 25 \cdot 10^9. Only 13 of these 4842 numbers are strong pseudoprimes to the bases 2, 3 and 5. The paper [4] has a listing of all strong pseudoprimes to the bases 2, 3 and 5 that are below 10^{12}. This listing has only 101 numbers. Only 9 these 101 numbers are strong pseudoprimes to bases 2, 3, 5 and 7. So there are indications that strong pseudoprimes are rare and that strong pseudoprimes to several bases are even rarer.

However, there are infinitely many strong pseudoprimes to a given base. In particular, there are infinitely many strong pseudoprimes to base 2 (two proofs are given in this previous post and in this previous post). According to what is said at the beginning of the post, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the first trillion prime bases! Furthermore, for these Carmichael numbers, any prime factors must be larger than the first trillion primes bases! It makes sense to examine this theorem so that we can further understand the implied results. The theorem is obviously a deep theoretical result, established by heavy duty machinery (theoretically speaking).

Fermat’s little theorem implies that if n happens to be a prime number, then n is a probable prime to all bases a that are relatively prime to n. It is easy to see that if n is a prime number, then n is a strong probable prime to all bases a that are relatively prime to n. Equivalently, if n is not a strong probable prime to some base a, then n is proved to be composite. Such a base a is said to be a witness for the compositeness of n. So a witness is a base, when used in the calculation for (1), will prove the compositeness of a number. Here’s one reason that the concept of strong pseudoprime is better than the concept of pseudoprime. If n is composite, there is at least one base that is a witness for n (see this previous post).

A Carmichael number is a composite number n such that it is a pseudoprime to all the bases relatively prime to n. Thus the Fermat test will never detect the compositeness of Carmichael numbers. On the other hand, the strong probable prime test (the Miller-Rabin test) will likely to give the correct result on Carmichael numbers.

Let n be an odd positive composite number. Let W(n) denote the smallest witness for the compositeness of n. Since any composite number has at least one witness, there is a least one. So W(n) is well defined. It is clear that W(n)>b if and only if n is a strong pseudoprime to all bases \le b. So any composite number that has a large least witness is a strong pseudoprime to many bases. The following is the statement of Theorem 1 of [1].

Theorem 1
There are infinitely many Carmichael numbers n such that

    \displaystyle W(n)> \text{ln}(n)^{\displaystyle \biggl[\frac{1}{3 \cdot \text{ln ln ln} \ n} \biggr]}=f(n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Furthermore, whenever x is sufficiently large, the number of such n below x is at least

    \displaystyle x ^{\displaystyle \biggl[\frac{1}{35 \cdot \text{ln ln ln} \ x}\biggr]}

We show how Theorem 2 is derived from Theorem 1.

Theorem 2
Given a finite set of bases, there are infinitely many Carmichael numbers that are strong pseudoprimes to all the bases in the finite set.

Proof of Theorem 2
Consider the function f(n) defined in the right-hand side of the inequality (2) in the statement of Theorem 1. The key facts about this function are that:

  • The function f(n) is an increasing function for sufficiently large n.
  • The function f(n) is increasing without bound, i.e., for each sufficiently large N, there exists an n such that f(n)>N.

We use these two facts to derive the intended results. These two key facts will be discussed at the end. By Theorem 1, there exist Carmichael numbers

    n_1 < n_2 < n_3 < \cdots

such that (2) holds for each term in the sequence, i.e., W(n_j)>f(n_j) for each j. Based on the key facts, the following sequence is increasing without bound.

    f(n_1),f(n_2),f(n_3),\cdots

Let B be a finite set of positive integers \ge 2. Choose some k such that for each j>k, f(n_j) is greater than all elements of B. Let m be the maximum of all the integers in the finite set B. Now it is clear that for each j>k, f(n_j)>m and that W(n_j)>m. It follows that for each of the following infinitely many Carmichael numbers

    n_{k+1} < n_{k+1} < n_{k+3} < \cdots

the least witness is greater than m. Thus all these Carmichael numbers are strong psuedoprimes to all bases \le m, hence to all the bases in the finite set B.

To see that the function f(n) is increasing pass some sufficiently large n, take the derivative of \text{ln} f(n).

    \displaystyle \text{ln} f(n)=\frac{\text{ln} \ n}{3 \ \text{ln ln ln} \ x}

    \displaystyle \begin{aligned} (\text{ln} f(n))^{'}&=\frac{3 \ \text{ln ln ln} \ n \ \displaystyle \frac{1}{n} - (\text{ln} \ n) \ 3 \ \displaystyle \frac{1}{\text{ln ln} \ n} \ \frac{1}{\text{ln} \ n} \ \frac{1}{n}}{(3 \ \text{ln ln ln} \ x)^2} \\&\text{ } \\&=\frac{ \displaystyle \frac{3 \ \text{ln ln ln} \ n}{n} - \displaystyle \frac{3}{n \ \text{ln ln} \ n} }{(3 \ \text{ln ln ln} \ x)^2} \\&\text { }\\&=\frac{3 \ (\text{ln ln ln} \ n) \ (\text{ln ln} \ n) - 3}{n \ \text{ln ln} \ n \ (3 \ \text{ln ln ln} \ x)^2}  \end{aligned}

The above derivative is positive if and only if the following is true:

    (\text{ln ln ln} \ n) \ (\text{ln ln} \ n) >1

This last inequality always holds for sufficiently large n. Thus for sufficiently large n, the derivative of f(n) is positive, meaning that f(n) is increasing.

To see that f(n) increases without bound, fix a sufficiently large N. Choose an integer j large enough such that e^j > N and e^j > 3j^2. Let n=e^k where \displaystyle k=e^{\displaystyle (e^{j})}. We have the following.

    \displaystyle \begin{aligned} f(n)&= f(e^k) \\&=k^{\displaystyle \biggl[\frac{1}{3 \ \text{ln ln \ k}}\biggr]} \\&=(e^{\displaystyle (e^{j})})^{\displaystyle \frac{1}{3j}} \\&=\displaystyle e^{\displaystyle \frac{e^j}{3j}} \\&>\displaystyle e^{\displaystyle \frac{3j^2}{3j}}=e^j>N  \end{aligned}

The above derivation shows that the function f(n) increases without bound. \blacksquare

Theorem 2 implies the following theorem. For the infinitely many Carmichael numbers that are strong pseudoprimes to all the bases below a bound, no prime numbers within the bound can be a factor for these Carmichael numbers.

Theorem 3
There are infinitely many Carmichael numbers that have no small prime factors.

The Carmichael numbers that are claimed to exist by Theorem 3 will likely not be detected as composite by factoring. For example, consider a Carmichael number that is a strong pseudoprime to all the prime bases below 2^{1024}. Its compositeness will likely not be detected by factoring based on the current computing technology and on the current factoring algorithms. This is another reason that the strong probable prime test (the Miller-Rabin test) is better than the Fermat test. The latter will declare the Carmichael number in question as prime while the former will likely be correct.

___________________________________________________________________

Example

Consider the following 397-digit number.

    C=
    28871482380507712126714295971303939919776094592797
    22700926516024197432303799152733116328983144639225
    94197780311092934965557841894944174093380561511397
    99994215424169339729054237110027510420801349667317
    55152859226962916775325475044445856101949404200039
    90443211677661994962953925045269871932907037356403
    22737012784538991261203092448414947289768854060249
    76768122077071687938121709811322297802059565867

The above is a 397-digit Carmichael number found in [3]. It is a strong pseudoprime to all the prime bases up to 300. According to Theorem 2, there are infinitely many other Carmichael numbers that are strong pseudoprimes to all the prime bases below 300. The number C is generated using the following formula.

    C=p_1 [313(p_1-1)+1] [353(p_1-1)+1]

    p_1=
    29674495668685510550154174642905332730771991799853
    04335099507553127683875317177019959423859642812118
    8033664754218345562493168782883

___________________________________________________________________

Reference

  1. Alford W., Granville A., and Pomerance C., On the difficulty of finding reliable witnesses, L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory: Proc. ANTS-I, Ithaca, NY, volume 877 of Lecture Notes in Computer Science, pages 1–16. Springer–Verlag, 1994.
  2. Alford W., Granville A., and Pomerance C., There are infinitely many Carmichael numbers, Ann. of Math. 139, 703-722, 1994.
  3. Arnault F., Constructing Carmichael numbers which are pseudoprimes to several bases, J. Symbolic Computation, 20, 151-161, 1995.
  4. Jaeschke G., On strong pseudoprimes to several bases, Math. Comp., Volume 61, No. 204, 915-926, 1993.
  5. Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
  6. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to 25 \cdot 10^9, Math. Comp., Volume 35, 1003-1026, 1980.

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

Large examples of strong pseudoprimes to several bases

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

___________________________________________________________________

The strong probable prime test

Given an odd number n whose “prime versus composite” status is not known, set n-1=2^k \cdot Q where k \ge 1 and Q is odd. Then calculate the following sequence of k+1 numbers:

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

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

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

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

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

___________________________________________________________________

Examples

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

    M=
    1195068768795265792518361315725116351898245581

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

    N=
    80383745745363949125707961434194210813883768828755
    81458374889175222974273765333652186502336163960045
    45791504202360320876656996676098728404396540823292
    87387918508691668573282677617710293896977394701670
    82304286871099974399765441448453411558724506334092
    79022275296229414984230688168540432645753401832978
    6111298960644845216191652872597534901

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

    M-1=2^2 \cdot Q

    N-1=2^2 \cdot R

where Q and R are odd and

    Q=
    298767192198816448129590328931279087974561395

    R=
    20095936436340987281426990358548552703470942207188
    95364593722293805743568441333413046625584040990011
    36447876050590080219164249169024682101099135205823
    21846979627172917143320669404427573474244348675417
    70576071717774993599941360362113352889681126583523
    19755568824057353746057672042135108161438350458244
    6527824740161211304047913218149383725

___________________________________________________________________

Random bases

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

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

    b=
    932423153687800383671087185189848318498417236

    c=
    23876349986768815408041169070899917334655923628776
    58344592618224528502905948639172375368742187714892
    08287654410018942444630244906406410549094447554821
    42803219639200974486541191341820595453041950723891
    75748815383568979859763861820607576949539863746244
    98291058421101888215044176056586791235119485393994
    789287924346696785645273545040760136

___________________________________________________________________

The calculation using random bases

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

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

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

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

where t_1, t_2 and t_3 are:

    t_1=
    1042866890841899880275968177787239559549445173

    t_2=
    826876320842405260107866407865475914456579581

    t_3=
    1195068768795265792518263537659322626328455738

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

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

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

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

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

where g_1, g_2 and g_3 are:

    g_1=
    43050290968654965761881145696359381339174664947842
    93659429396009893693594328847691223585119425166890
    43134041173054778367051375333950357876719375530986
    40705386242996844394887879855798166233504226845778
    76290707027478869178569806270616567220414388766208
    75314254126730991658967210391794715621886266557484
    525788655243561737981785859480518172

    g_2=
    69330060289060873891683879069908453474713549543545
    79381982871766126161928753307995063953670075390874
    26152164526384520359363221849834543643026694082818
    11219470237408138833421506246436132564652734265549
    18153992550152009526926092009346342470917684117296
    93655167027805943247124949639747970357553704408257
    9853042920364675222045446207932076084

    g_3=
    80383745745363949125707961434194210813883768828755
    81458374889175222974273765333652186502336163960045
    45791504202360320876656996676098728404396540823292
    87387918508691668493091034289810372813316104284761
    45244183107779151749589951324358651494383103941607
    35777636976785468267798055151468799251924355070195
    1772723904683953622590747688533861698

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

___________________________________________________________________

Some verification

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

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

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

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

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

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

where

    w_1=
    977597583337476418144488003654858986215112009

    w_2=
    368192447952860532410592685925434163011455842

    w_3=
    1195068768795265792518263537659322626328455738

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

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

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

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

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

    __________________

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

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

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

    __________________

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

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

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

where

    v_1=
    48799236892584399744277334997653638759429800759183
    35229821626086043683022014304157526246067279138485
    99367014952239377476103536546259094903793421522217
    99291447356172114871135567262925519534270746139465
    22832800077663455346130103616087329184090071367607
    57478119260722231575606816699461642864577323331271
    2974554583992816678859279700007174348

    v_2=
    80191643327899921083661290416909370601037633208226
    50175490124094760064341402392485432446383194439467
    16432633017071633393829046762783433857505596089159
    3600905184063673203

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

___________________________________________________________________

Remark

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

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

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

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

___________________________________________________________________

Reference

  1. Alford W., Granville A., and Pomerance C., On the difficulty
    of finding reliable witnesses
    , L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory: Proc. ANTS-I, Ithaca, NY, volume 877 of
    Lecture Notes in Computer Science, pages 1–16. Springer–Verlag, 1994.
  2. Arnault F., Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Computation, 20, 151-161, 1995.
  3. Arnault F., Rabin-Miller primality test: composite numbers that pass it, Math. Comp., Volume 64, No. 209, 355-361, 1995.
  4. Jaeschke G., On strong pseudoprimes to several bases, Math. Comp., Volume 61, No. 204, 915-926, 1993.
  5. Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
  6. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to 25 \cdot 10^9, Math. Comp., Volume 35, No. 151, 1003-1026, 1980.

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

Looking for a good witness

For some primality tests, the approach of proving a number as composite is to produce an auxiliary number that shows that a property of prime numbers is violated. Such an auxiliary number is called a “witness” for compositeness. When using such a primality test on a composite number, for the test to be correct, at least one “witness” must be found. In this post, we compare the Fermat primality test and the Miller-Rabin test from the standpoint of producing “witnesses”. In this regard, the Fermat test works correctly most of the time. But there is a rare but infinite class of composite numbers for which no Fermat test witness can be found. On the other hand, using the Miller-Rabin test on a composite number, at least one witness can be found (in fact, there are lots of them).

___________________________________________________________________

Fermat witnesses

According to Fermat’s little theorem, if n is a prime number, then the following congruence holds for all numbers a that are coprime to n.

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

If there exists a number a such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then n is proved to be composite, in which case the number a is said to be a Fermat witness for the compositeness of n. If the congruence (1) holds for several values of a, then n is a likely a prime.

Suppose n is a large odd number whose “prime versus composite” status is not known. If the congruence (1) holds for some positive integer a, then n is said to be a probable prime to base a. A probable prime to the base a could be prime or could be composite. If the latter, the number n is said to be a pseudoprime to base a.

This is how the Fermat test (or probable prime test) works. Given that n is a large odd number whose “prime versus composite” status is not known, if n is not a probable prime to one base a, then n is proven to be composite and a is a Fermat witness for n. On the other hand, if n is a probable prime to several randomly selected bases, then n is a probable prime.

Suppose that you apply the Fermat test on the number n and find that n is a probable prime to several bases. There are two possibilities. Either n is prime or is a pseudoprime to the several bases that are being used. Pseudoprimess to one base are rare. Pseudoprimes to several bases at once are even rarer. For example, according to [3], there are only 21853 pseudoprimes to the base 2 that are less than 25 \cdot 10^9. The number of primes below 25 \cdot 10^9 is roughly 10^9. So most probable primes to base 2 are primes. Of the 21853 pseudoprimes to the base 2 that are below 25 \cdot 10^9, 4709 of them are pseudoprimes to the bases 2 and 3, 2522 of them are pseudoprimes to the bases 2, 3 and 5, and 1770 of them are pseudoprimes to the bases 2, 3, 5 and 7. Thus there is indication that the numbers that are pseudoprimes to several bases are very rare. Therefore, the number n being a simultaneous pseudoprime to several bases is very strong evidence that n is prime. But this is not the end of the story for the Fermat test.

The Fermat test can detect the compositeness of most composite numbers. These are the numbers n that are probable prime to one base but are not probable prime to another base. For example, 341 is a probable prime to base 2 since 2^{340} \equiv 1 \ (\text{mod} \ 341). On the other hand, 3^{340} \equiv 56 \ (\text{mod} \ 341). Thus 341 is not a probable prime to base 3 (i.e. 3 is a Fermat witness for the compositeness of 341). For integers like 341, they may be probable primes to one base, but they are not probable primes to another base. If there exists at least one Fermat witness for a composite number, there is a good chance that the Fermat test will detect the compositeness.

A odd composite number n is said to be a Carmichael number if the congruence (1) holds for all numbers a coprime to n. The smallest Carmichael number is 561. There is no danger of mistaking a small Carmichael number such as 561 as prime because factoring is possible. Carmichael numbers are rare but there are infinitely of them. So there are large Carmichael numbers (e.g. with hundreds of digits or thousands of digits). The Fermat test fails completely with these large Carmichael numbers. In other words, no matter how many bases are used, it is impossible to find a number a that will witness the compositeness of a Carmichael number. Unlike the number 341, the Fermat test will fail to detect the compositeness of a Carmichael number.

___________________________________________________________________

Looking for a better type of witness

Let n be an odd number with n-1=2^k \cdot Q where k \ge 1 and Q is odd. Then compute the following sequence of k+1 numbers modulo n:

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

where a is some number coprime to n. The first term in the sequence can be calculated by using the fast powering algorithm. Each subsequent term is the square of the preceding one. Of course, the last term is the same as a^{n-1}, the calculation for (1). Then if this calculation is done on a prime number n, the last term in (2) is always a 1. But more can be said about the sequence (2).

The better witnesses and primality test we discuss here are based on this theorem about prime numbers.

    If n is a prime number, then either one of the following conditions holds:

    • \displaystyle a^{Q} \equiv 1 \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2a)
    • \displaystyle a^{2^j \cdot Q} \equiv -1 \ (\text{mod} \ n) for some j=0,1,2,\cdots, k-1 \ \ \ \ \ \ \ \ (2b)

    \text{ }

    for each number a that is coprime to n.

The theorem just mentioned is the basis of the Miller-Rabin test. If there exists some a such that both (2a) and (2b) are not true, then the number n is proved to be composite, in which case the number a is said to be a witness for the compositeness of n. So a witness from the Fermat test standpoint is called Fermat witness. The term witness here refers to the calculation of (2). If the conditions (2a) or (2b) holds for several values of a, then n is likely a prime number.

Suppose n is a large odd number whose “prime versus composite” status is not known. If the conditions (2a) or (2b) holds for some positive integer a, then n is said to be a strong probable prime to base a. A strong probable prime to the base a could be prime or could be composite. If the latter, the number n is said to be a strong pseudoprime to base a.

This is how the Miller-Rabin test (or strong probable prime test) works. Given that n is a large odd number whose “prime versus composite” status is not known, if n is not a strong probable prime to one base a, then n is proved to be composite and the number a is a witness for a. If n is a strong probable prime to several randomly chosen bases, then the probability that n is composite is smaller than 4^{-k} (if k bases are used). In other words, the error probability can be made arbitrarily small by using more random bases in the calculation for sequence (2).

The last point about the small error probability is the most important advantage of the Miller-Rabin test over the Fermat test. Let’s look at a small example first. Recall that 561 is the smallest Carmichael number. Note that 560=2^4 \cdot 35. The following is the calculation for (2).

    2^{35} \equiv 263 \ (\text{mod} \ 561)

    2^{2 \cdot 35} \equiv 166 \ (\text{mod} \ 561)

    2^{4 \cdot 35} \equiv 67 \ (\text{mod} \ 561)

    2^{8 \cdot 35} \equiv 1 \ (\text{mod} \ 561)

    2^{16 \cdot 35} \equiv 1 \ (\text{mod} \ 561)

The number 561 is a probable prime to base 2 (from a Fermat perspective). Notice that the condition (2a) is not met. The condition (2b) is also not met since the term preceding the first 1 is 67, which is not congruent to -1. So the number 2 is a witness for the compositeness of 561. The Fermat test will have virtually no chance of detecting the compositeness of 561. Yet the strong probable prime test takes only one calculation for 561. In this case at least, it is pretty easy to find a witness.

___________________________________________________________________

At least one witness can be found

One characteristic of the strong probable prime test is that there are lots of witnesses when testing composite numbers. In fact, if n is a composite number, over 75% of the possible choices of bases a are witnesses for n. We prove a simpler theorem that if n is composite, at least one witness for the compositeness of n can be found. Even this much weaker theorem is a big improvement over the Fermat test.

Theorem 1
Let n be a composite positive odd number. Then there a number a that is coprime to n such that n is not a strong pseudoprime to base a.

Proof of Theorem 1
Let n=u \cdot v such that u,v are odd and are coprime. Consider the following two congruence equations.

    x \equiv 1 \ (\text{mod} \ u)

    x \equiv -1 \ (\text{mod} \ v)

By the Chinese remainder theorem (CRT), there is an a such that

    a \equiv 1 \ (\text{mod} \ u)

    a \equiv -1 \ (\text{mod} \ v)

We can assume that 1<a<n. If not, reduce a modulo n. Then a \not \equiv 1 \ (\text{mod} \ n). If a \equiv 1 \ (\text{mod} \ n), then a=1+n \cdot t=1+u \cdot v \cdot t for some t. This would mean that a \equiv 1 \ (\text{mod} \ v), contradicting a \equiv -1 \ (\text{mod} \ v). Similarly a \not \equiv -1 \ (\text{mod} \ n). So we have a \not \equiv \pm 1 \ (\text{mod} \ n). On the other hand, we have

    a^2 \equiv 1 \ (\text{mod} \ u)

    a^2 \equiv 1 \ (\text{mod} \ v)

By CRT, a^2 \equiv 1 \ (\text{mod} \ n). Let n-1=2^k \cdot Q where k \ge 1 and Q odd. Let Q=2w+1 for some integer w. The following calculates a^Q and a^{2 \cdot Q}.

    a^Q=a^{2w} \cdot a = (a^2)^w \cdot a \equiv 1^w \cdot a \equiv a \not \equiv \pm 1 \ (\text{mod} \ n)

    a^{2 \cdot Q} \equiv (a^2)^Q \equiv (1)^Q \equiv 1 \ (\text{mod} \ n)

The first term in (2) that is a 1 is a^{2 \cdot Q}. The preceding term is not a -1. This shows that the composite number n is not a strong pseudoprime to base a. Thus for any composite number n, there always exists a witness for the compositeness of n. \blacksquare

The proof of Theorem 1 is essentially that if n is composite, there is a square root other than \pm 1. This nontrivial square root is a witness to the compositeness of n.

___________________________________________________________________

The least witness

If n is a composite number, there exists a witness for n according to Theorem 1. Of all the witnesses for a given composite number n, there must be the smallest one. Let w(n) be the least witness for the compositeness for the composite number n. The number w(n) is an interesting one.

In general, the larger w(n) is, the harder to find the number n. This stems from the fact that strong pseudoprimes are very rare. Most composite numbers are not strong pseudoprimes to base 2. For these composite numbers, w(n)=2. For the strong pseudoprimes to base 2, w(n)>2. For w(n)>3, the composite numbers must be strong pseudoprimes to base 2 and base 3. For w(n)>5, the composite numbers must be strong pseudoprimes to the prime bases 2, 3 and 5. There are only 13 such numbers below 25 \cdot 10^9. Thus it is not easy to find composite numbers that have large least witnesses.

Two more comments to make. One is that knowing the least integer n such that w(n) is greater than the first k prime numbers can be as a deterministic primality test [2]. This is discussed in the next post. The other is that even though a large w(n) means that the composite numbers n are rare (under a specific bound). But there are infinitely many of them (over the entire number line). It follows from a theorem in [1] that for any finite set of integers, there are infinitely many Carmichael numbers whose w(n) is not found in the finite set.

___________________________________________________________________

Reference

  1. Alford W., Granville A., and Pomerance C., On the difficulty
    of finding reliable witnesses
    , L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory: Proc. ANTS-I, Ithaca, NY, volume 877 of
    Lecture Notes in Computer Science, pages 1–16. Springer–Verlag, 1994.
  2. Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
  3. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to 25 \cdot 10^9, Math. Comp., Volume 35, 1003-1026, 1980.

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

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

    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}

The Fermat primality test

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
    If n is a prime number and if a is an integer that is relatively prime to n, then the following congruence relationship holds:

      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
    The test is to determine whether a large positive integer n is prime or composite. The test will output one of two results: n is Composite or n is 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
    Let n be a composite integer such that it is not a pseudoprime to at least one base (i.e. n has a Fermat witness). In other words, n is not a Carmichael number. Then n is not a pseudoprime to at least half of the bases a (1<a<n) that are relatively prime to n. In other words, n is a pseudoprime to at most half of the bases a (1<a<n) that are relatively prime to 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
    If b is a number such that 1<b<n and such that n is a pseudoprime to base b, then n is not a pseudoprime to base 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
    Let n be a composite integer such that it is not a pseudoprime to at least one base. Then n is not a pseudoprime to at least \displaystyle \frac{\phi(n)}{2} many bases in the interval 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

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:

    When the congruence (1) is satisfied for one base a, is that enough evidence to conclude that n is prime?

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} where \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

  1. Pomerance C., On the distribution of pseudoprimes, Math. Comp., Volume 37, 587-593, 1981.
  2. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to 25 \cdot 10^9, Math. Comp., Volume 35, 1003-1026, 1980.

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