A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes". Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all coprime bases (the Carmichael numbers), 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 (PRP). We pick base a = 3 and, inspired by Fermat's little theorem, calculate:
3 31696 ≡ 1 ( mod 31697 ) {\displaystyle 3^{31696}\equiv 1{\pmod {31697}}}
This shows 31697 is a Fermat PRP (base 3), so we may suspect it is a prime. We now repeatedly halve the exponent:
3 15848 ≡ 1 ( mod 31697 ) {\displaystyle 3^{15848}\equiv 1{\pmod {31697}}}
3 7924 ≡ 1 ( mod 31697 ) {\displaystyle 3^{7924}\equiv 1{\pmod {31697}}}
3 3962 ≡ 28419 ( mod 31697 ) {\displaystyle 3^{3962}\equiv 28419{\pmod {31697}}}
The first couple of times do not yield anything interesting (the result was still 1 modulo 31697), but at exponent 3962 we see a result that is neither 1 nor −1 (i.e. 31696) modulo 31697, proving 31697 is composite, and therefore not a strong pseudoprime to base 3. Modulo a prime, the residue 1 can have no other square roots than +1 and −1, but if the modulus is composite, 1 can have square root +1 modulo some factors and −1 modulo others, leading to additional possibilities. In cases like this, where a number is a Fermat pseudoprime but not a strong pseudoprime, this even gives us a factorization: 31697 = gcd(28419+1, 31697) × gcd(28419−1, 31697) = 29 × 1093. For another example, pick n = 47197 and calculate in the same manner:
3 47196 ≡ 1 ( mod 47197 ) {\displaystyle 3^{47196}\equiv 1{\pmod {47197}}}
3 23598 ≡ 1 ( mod 47197 ) {\displaystyle 3^{23598}\equiv 1{\pmod {47197}}}
3 11799 ≡ 1 ( mod 47197 ) {\displaystyle 3^{11799}\equiv 1{\pmod {47197}}}
In this case, the result continues to be +1 (mod 47197) 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 (can be seen by picking other bases than 3), we have that 47197 is a strong pseudoprime to base 3. Finally, consider n = 74593 where we get:
3 74592 ≡ 1 ( mod 74593 ) {\displaystyle 3^{74592}\equiv 1{\pmod {74593}}}
3 37296 ≡ 1 ( mod 74593 ) {\displaystyle 3^{37296}\equiv 1{\pmod {74593}}}
3 18648 ≡ 74592 ≡ − 1 ( mod 74593 ) {\displaystyle 3^{18648}\equiv 74592\equiv -1{\pmod {74593}}}
Here, we reach minus −1 modulo 74593, a situation that is perfectly possible with a prime. When this occurs, we stop the calculation (even though the exponent is not odd yet) and say that 74593 is a strong probable prime (and, as it turns out, a strong pseudoprime) to base 3.
Formal definition An odd composite number n = d · 2s + 1 where d is odd is called a strong (Fermat) pseudoprime to base a if:
a d ≡ 1 ( mod n ) {\displaystyle a^{d}\equiv 1{\pmod {n}}}
or
a d ⋅ 2 r ≡ − 1 ( mod n ) for some 0 ≤ r < s . {\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad {\mbox{ for some }}0\leq r<s.}
(If a number n satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base a. But if we know that n is not prime, then we may use the term strong pseudoprime.) The definition is trivially met if a ≡ ±1 (mod n) so these trivial bases are often excluded. Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.
… excerpt ends here. Continue reading the full article.
