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}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s