Miller-Rabin pseudoprimality test

The Miller-Rabin pseudoprimality test is based in two facts for prime numbers:

• The Fermat Little Theorem that states: ${\displaystyle a^{p-1}\equiv 1(\mathrm{mod}p)}$.
• If ${\displaystyle m^2\equiv 1(\mathrm{mod}p)}$ then ${\displaystyle m\equiv 1(\mathrm{mod}p)}$ or ${\displaystyle m\equiv -1(\mathrm{mod}p)}$.

Let ${\displaystyle N}$ be an odd number being tested for primality, and ${\displaystyle N=2^{n}k+1}$ where ${\displaystyle k}$ is an odd number.

Then consider the sequence ${\displaystyle a^k}$, ${\displaystyle a^{2k}}$, ${\displaystyle a^{4k}}$..., ${\displaystyle a^{N-1}}$ modulo ${\displaystyle N}$. This sequence should end with 1 because of the Fermat Little theorem.

If a member of the sequence is 1 but the previous is not 1 or -1, or the last member is not 1, the number is composite.

Otherwise the number is either a prime or a Miller-Rabin pseudoprime (sometimes called a strong pseudoprime) with respect to base ${\displaystyle a}$.

Usually, several tests are performed with different bases in order to increase the confidence that the number is not composite. If ${\displaystyle k}$ different random pairwise-relatively-prime bases less than ${\displaystyle N}$ are choosen for the Miller-Rabin test, and ${\displaystyle N}$ passes all ${\displaystyle k}$ tests, then the probability that N is composite is less than ${\displaystyle {1/4}^k}$. Conversely, it can be demonstrated that a composite ${\displaystyle N}$ will only pass at most ${\displaystyle (N-1)/4}$ such tests.

Factoring Fermat pseudoprimes

Many pseudoprimes that pass the Fermat pseudoprimality test can be factored using the sequence defined above.

When ${\displaystyle a^{(2^{r}k)}\not\equiv \pm 1(\mathrm{mod}N)}$ and ${\displaystyle a^{(2^{r+1}k)}\equiv 1(\mathrm{mod}N)}$, a proper factor of ${\displaystyle N}$ is:

${\displaystyle gcd(N,a^{(2^{r}k)}+1modN)}$

Another proper factor is:

${\displaystyle gcd(N,a^{(2^{r}k)}-1modN)}$

Example

Let N = 561. Then N-1 = 2⁴ × 35. Since the exponent is 4, the sequence will use exponents from zero to 4.

The Miller-Rabin sequence for base 5 is:

• r = 0: ${\displaystyle 5^{35}\equiv 23(\mathrm{mod}561)}$
• r = 1: ${\displaystyle {23}^2\equiv 529(\mathrm{mod}561)}$
• r = 2: ${\displaystyle {529}^2\equiv 463(\mathrm{mod}561)}$
• r = 3: ${\displaystyle {463}^2\equiv 67(\mathrm{mod}561)}$
• r = 4: ${\displaystyle {67}^2\equiv 1(\mathrm{mod}561)}$

Notice that in this case the number is a Fermat pseudoprime, because the sequence ends with the number 1, but according with the Miller-Rabin test the number is definitely composite, because before the number 1 we got a number which is not 1 or 560.

If we want to find factors of this number we can perform:

gcd(67-1, 561) = 33

gcd(67+1, 561) = 17

External links

• Wikipedia