Miller-Rabin pseudoprimality test

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

• The Fermat Little Theorem that states: [math]\displaystyle{ a^{p-1}\equiv 1\,\pmod p }[/math].
• If [math]\displaystyle{ m^2\equiv 1\,\pmod p }[/math] then [math]\displaystyle{ m\equiv 1\,\pmod p }[/math] or [math]\displaystyle{ m\equiv -1\,\pmod p }[/math].

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

Then consider the sequence [math]\displaystyle{ a^k }[/math], [math]\displaystyle{ a^{2k} }[/math], [math]\displaystyle{ a^{4k} }[/math]..., [math]\displaystyle{ a^{N-1} }[/math] modulo [math]\displaystyle{ N }[/math]. 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 [math]\displaystyle{ a }[/math].

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

Factoring Fermat pseudoprimes

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

When [math]\displaystyle{ a^{(2^r\,k)}\not\equiv \pm 1\,\pmod N }[/math] and [math]\displaystyle{ a^{(2^{r+1}\,k)}\equiv 1\,\pmod N }[/math], a proper factor of [math]\displaystyle{ N }[/math] is:

[math]\displaystyle{ gcd(N, a^{(2^r\,k)} + 1\bmod N) }[/math]

Another proper factor is:

[math]\displaystyle{ gcd(N, a^{(2^r\,k)} - 1\bmod N) }[/math]

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: [math]\displaystyle{ 5^{35}\equiv 23\,\pmod{561} }[/math]
• r = 1: [math]\displaystyle{ 23^2\equiv 529\,\pmod{561} }[/math]
• r = 2: [math]\displaystyle{ 529^2\equiv 463\,\pmod{561} }[/math]
• r = 3: [math]\displaystyle{ 463^2\equiv 67\,\pmod{561} }[/math]
• r = 4: [math]\displaystyle{ 67^2\equiv 1\,\pmod{561} }[/math]

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