In number theory, a probable prime is a number that passes a primality test. A strong probable prime is a number that passes a strong version of a primality test. A strong pseudoprime is a composite number that passes a strong version of a primality test. All primes pass these tests, but a small fraction of composites also pass, making them "false primes". Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all coprime bases, there are no composites that are strong pseudoprimes to all bases.
Motivation and first examples
Let us say we want to investigate if n = 31697 is a probable prime. We pick base a = 3 and, inspired by Fermat's little theorem, calculate: This shows 31697 is a Fermat PRP, so we may suspect it is a prime. We now repeatedly half the exponent: The first couple of times do not yield anything interesting, but at exponent 3962 we see a result that is neither 1 nor minus 1 modulo 31697. This proves 31697 is in fact composite. Modulo a prime, the residue 1 can have no other square roots than 1 and minus 1. This shows that 31697 is not a strong pseudoprime to base 3. For another example, pick n = 47197 and calculate in the same manner: In this case, the result continues to be 1 until we reach an odd exponent. In this situation, we say that 47197 is a strong probable prime to base 3. Because it turns out this PRP is in fact composite, we have that 47197 is a strong pseudoprime to base 3. Finally, consider n = 74593 where we get: Here, we reach minus 1 modulo 74593, a situation that is perfectly possible with a prime. When this occurs, we stop the calculation and say that 74593 is a strong probable prime to base 3.
Formal definition
An odd composite number n = d · 2s + 1 where d is odd is called a strong pseudoprime to base a if: or The definition is trivially met if so these trivial bases are often excluded. Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.
Properties of strong pseudoprimes
A strong pseudoprime to base a is always an Euler–Jacobi pseudoprime, an Euler pseudoprime and a Fermat pseudoprime to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Carmichael numbers may be strong pseudoprimes to some bases—for example, 561 is a strong pseudoprime to base 50—but not to all bases. A composite number n is a strong pseudoprime to at most one quarter of all bases below n; thus, there are no "strong Carmichael numbers", numbers that are strong pseudoprimes to all bases. Thus given a random base, the probability that a number is a strong pseudoprime to that base is less than 1/4, forming the basis of the widely used Miller–Rabin primality test. However, Arnault gives a 397-digit Carmichael number that is a strong pseudoprime to every base less than 307. One way to reduce the chance that such a number is wrongfully declared probably prime is to combine a strong probable prime test with a Lucas probable prime test, as in the Baillie–PSW primality test. There are infinitely many strong pseudoprimes to any base.
Examples
The first strong pseudoprimes to base 2 are The first to base 3 are The first to base 5 are For base 4, see, and for base 6 to 100, see to. By testing the above conditions to several bases, one gets somewhat more powerfulprimality tests than by using one base alone. For example, there are only 13 numbers less than 25·109 that are strong pseudoprimes to bases 2, 3, and 5 simultaneously. They are listed in Table 7 of. The smallest such number is 25326001. This means that, if n is less than 25326001 and n is a strong probable prime to bases 2, 3, and 5, then n is prime. Carrying this further, 3825123056546413051 is the smallest number that is a strong pseudoprime to the 9 bases 2, 3, 5, 7, 11, 13, 17, 19, and 23. So, if n is less than 3825123056546413051 and n is a strong probable prime to these 9 bases, then n is prime. By judicious choice of bases that are not necessarily prime, even better tests can be constructed. For example, there is no composite that is a strong pseudoprime to all of the seven bases 2, 325, 9375, 28178, 450775, 9780504, and 1795265022.
