Strong pseudoprime

Definition

Suppose $n$ is an odd composite natural number and $a$ is an integer relatively prime to $n$. We say that $n$ is a strong pseudoprime (also called Miller-Rabin pseudoprime, Rabin-Miller pseudoprime, Miller-Rabin strong pseudoprime, Rabin-Miller strong pseudoprime) to base $a$ if the following holds.

Write $n-1=2^{k}s$ where $s$ is odd and $k$ is a nonnegative integer. Then, either one of these conditions should hold:

• $a^{s}\equiv 1{\pmod {n}}$.
• $a^{n-1}\equiv 1{\pmod {n}}$. Further, consider the smallest $l$ for which $a^{2^{l}s}\equiv 1{\pmod {n}}$. Then, $a^{2^{l-1}s}\equiv -1{\pmod {n}}$. In other words, the last value before becoming $1$ should be $-1$.

The name strong pseudoprime is because the above condition is satisfied for all primes, and is a particularly strong condition for which finding composite numbers is hard.

Relation with other properties

Weaker properties

• Euler pseudoprime
• Fermat pseudoprime