A strong pseudoprime to base is a composite number that passes the strong probable prime test (i.e. the Miller-Rabin test) in the base . There are indications that strong pseudoprimes are rare. According to , there are only 4842 numbers below that are strong pseudoprimes to base 2. Strong pseudoprimes to several bases are even rarer. According to , there are only 13 numbers below that are strong pseudoprimes to bases 2, 3 and 5. The paper  tabulates the numbers below 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 whose “prime versus composite” status is not known, set where and is odd. Then calculate the following sequence of numbers:
where is some integer relatively prime to . The first term can be efficiently calculated using the fast powering algorithm. Each subsequent term is the square of the preceding term. Each term is reduced modulo .
If (i.e. the first term in sequence (1) is a 1) or for some (i.e. the term preceding the first 1 in the sequence is a -1), then is said to be a strong probable prime to the base . A strong probable prime to base could be a prime or could be composite. If the latter, it is said to be a strong pseudoprime to base . In fact, most strong probable primes to one base are prime.
The strong probable prime test consists of checking whether is a strong probable prime to several bases. If is not a strong probable prime to one of the bases, then is composite for sure. If is a strong probable prime to all of the bases being used, then is likely a prime number in that the probability that it is composite is at most if is the number of bases.
The last probability of is what makes the 337-digit number 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.
The following is a 46-digit found in  that is a strong pseudoprime to the first 11 prime bases (the prime numbers from 2 to 31).
The following is a 337-digit number found in  that is a strong pseudoprime to all 46 prime bases up to 200 (the prime numbers from 2 to 199).
The following sets up the calculation for the Miller-Rabin test (strong probable prime test).
where and are odd and
Though the second number is very striking, the author of  has an even larger example in , 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 and using some random bases. Consider the following randomly chosen bases and where and .
The calculation using random bases
Here’s the calculation for the 46-digit number .
where , and are:
Note that the last number is not a 1. So the number is not a strong probable prime to base . This means that it is composite.
Here’s the calculation for the 337-digit number .
where , and are:
Interestingly, the last number agrees with the modulus from the first digit (the largest) to digit 167. It is clear that is clearly not a 1. So the 337-digit number is not a strong probable prime to base , meaning it is composite. Even though the number 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.
We also verify that the 46-digit is a strong pseudoprime to the first 11 prime bases.
The asterisks in the above table mean that those cells have numbers that are modulo . Clearly the table shows that the number passes the strong probable prime test for these 11 bases. We also verify that is not a strong probable prime to base 37, the next prime base.
Note that the last number agrees with the modulus for the first 22 digits and they differ in the subsequent digits. It is clear that is not 1. So the strong pseudoprimality of stops at the base 37.
We do not verify the number for all the 46 prime bases. We only show partial verification. The following calculation shows the pseudoprimality of to bases 197 and 199, and that the strong pseudoprimality of fails at 211, the next prime base.
Note that is clearly not congruent to -1. Thus the number is not a strong pseudoprime to base 211 (though it is a pseudoprime to base 211). Clearly, the above calculation indicates that the number is a strong pseudoprime to bases 197 and 199.
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 prime bases . 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  lists 101 strong pseudoprimes to bases 2, 3 and 5 that are below . This test is fast and easy to use; it requires only three modular exponentiations to determine the primality of numbers less than .
The numbers and are not Carmichael numbers since and , making the random numbers and Fermat witnesses for these two numbers respectively. Another way to see that they are not Carmichael is that each of the two number and is also a product of two distinct primes according to .
An even more striking result than the examples of and is that it follows from a theorem in  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.
- 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.
- Arnault F., Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Computation, 20, 151-161, 1995.
- Arnault F., Rabin-Miller primality test: composite numbers that pass it, Math. Comp., Volume 64, No. 209, 355-361, 1995.
- Jaeschke G., On strong pseudoprimes to several bases, Math. Comp., Volume 61, No. 204, 915-926, 1993.
- Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
- Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to , Math. Comp., Volume 35, No. 151, 1003-1026, 1980.