 Strong pseudoprime

Let $N>2$ be an odd integer that is a composite number and write $N-1=2^{s}m$ with $m$ odd. For a base $b$ coprime to $N$, it is a strong pseudoprime whenThese are exactly the passing outcomes of the Miller-Rabin primality test for that base. The test computes $b^m$ by modular exponentiation and repeatedly squares it, looking for the permitted value $-1$ before reaching exponent $N-1$.

Every strong pseudoprime to a base is a Fermat pseudoprime to that base, by squaring a permitted congruence sufficiently many times. The converse fails. For $N=341$, one has $N-1=4\cdot 85$ and $2^{85}\equiv 32$, $2^{170}\equiv 1(\mathrm{mod}341)$. Neither tested residue is $-1$, and the first is not $1$, so base two detects compositeness even though $2^{340}\equiv 1(\mathrm{mod}341)$.