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 </math>n-1 = 2^k s</math> where $s$ is odd and $k$ is a nonnegative integer. Then, either one of these conditions should hold:

• $a^s\equiv 1(\mathrm{mod}n)$.
• $a^{n-1}\equiv 1(\mathrm{mod}n)$. Further, consider the smallest $l$ for which $a^{2^{l}s}\equiv 1(\mathrm{mod}n)$. Then, $a^{2^{l-1}s}\equiv -1(\mathrm{mod}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