Strong pseudoprime
= Strong pseudoprime
{wiki}
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> when
$$
b^m\equiv1\pmod N\quad\text{or}\quad b^{2^j m}\equiv-1\pmod N\quad\text{for some }0\leq j<s.
$$
These 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\cdot85$ and $2^{85}\equiv32$, $2^{170}\equiv1\pmod{341}$. Neither tested residue is $-1$, and the first is not $1$, so base two detects compositeness even though $2^{340}\equiv1\pmod{341}$.