A strong pseudoprime to a base a is an odd composite number n with n - 1 = d·2^s (for d odd) for which either a^d congruent 1 (mod n) or a^(d·2^r) congruent -1 (mod n) for some r = 0, 1, ..., s - 1. Note that Guy restricts the definition of strong pseudoprimes to only those satisfying (-2). The definition is motivated by the fact that a Fermat pseudoprime n to the base b satisfies b^(n - 1) - 1 congruent 0 (mod n).

Baillie-PSW primality test | Carmichael number | Miller's primality test | Poulet number | pseudoprime | Rabin-Miller strong pseudoprime test | Rotkiewicz theorem | strong elliptic pseudoprime | strong Lucas pseudoprime