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.

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:

This shows 31697 is a Fermat PRP (base 3), so we may suspect it is a prime. We now repeatedly halve the exponent:

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 minus 1 (i.e. 31696) modulo 31697. This proves 31697 is in fact composite (it equals 29×1093). 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 (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: