Topics Register • News • History • How to • Sequences statistics • Template prototypes

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\,\pmod p }$.
• If $\displaystyle{ m^2\equiv 1\,\pmod p }$ then $\displaystyle{ m\equiv 1\,\pmod p }$ or $\displaystyle{ m\equiv -1\,\pmod 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\,\pmod N }$ and $\displaystyle{ a^{(2^{r+1}\,k)}\equiv 1\,\pmod N }$, a proper factor of $\displaystyle{ N }$ is:

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

Another proper factor is:

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

Example

Let N = 561. Then N-1 = 24 × 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\,\pmod{561} }$
• r = 1: $\displaystyle{ 23^2\equiv 529\,\pmod{561} }$
• r = 2: $\displaystyle{ 529^2\equiv 463\,\pmod{561} }$
• r = 3: $\displaystyle{ 463^2\equiv 67\,\pmod{561} }$
• r = 4: $\displaystyle{ 67^2\equiv 1\,\pmod{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