MILLER-RABIN PRIMALITY TEST

The 'Miller-Rabin primality test' or 'Rabin-Miller primality test' is a primality test: an algorithm
which determines whether a given number is prime,
similar to the Fermat primality test and the Solovay-Strassen primality test. Its original version, due to Gary L. Miller, is deterministic, but it relies on the unproven generalized Riemann hypothesis; Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm.

Contents

Concepts

Example

Algorithm and running time

Sample Code

2 return false if n

Accuracy of the test

Deterministic variants of the test

References

External links

Concepts

Just like with the Fermat and Solovay-Strassen tests, with the Miller-Rabin test we will rely on an equality or set of equalities that hold true for prime values, and then see whether or not they hold for a number that we want to test for primality.
First, a lemma about square roots of unity in the finite field $mathbb\{Z\}/pmathbb\{Z\}$, where ''p'' is prime. Certainly 1 and -1 always yield 1 when squared mod ''p''; call these ''trivial'' square roots of 1. There are no ''nontrivial'' square roots of 1 mod $p$ (a special case of the result that in a field, a polynomial has no more zeroes than its degree). To show this, suppose that ''x'' is a square root of 1 mod ''p''. Then:
:$$
x^{2} equiv 1pmod{p}

:$$
left (x - 1
ight ) left ( x + 1
ight ) equiv 0pmod{p}

Since ''x'' is not 1 or -1 mod ''p'', neither $x-1$ nor $x+1$ is divisible by ''p''. But if a prime divides neither of two integers, it cannot divide their product.
Now, let ''n'' be an odd prime, then we can write ''n'' − 1 as $2^s\; cdot\; d$, where ''s'' is an integer and ''d'' is odd -- this is the same as factoring out 2 from ''n'' − 1 repeatedly. Then, one of the following must be true for all $ain\; left(mathbb\{Z\}/nmathbb\{Z\}$
ight)^
★ :
:$$
a^{d} equiv 1pmod{n}

or
:$$
a^{2^rcdot d} equiv -1pmod{n} for some $0\; le\; r\; le\; s-1$

To show that one of these must be true, recall Fermat's little theorem (which only applies for prime moduli):
:$$
a^{n-1} equiv 1pmod{n}

By the lemma above, if we keep taking square roots of ''a''^{''n'' − 1}, we will either get 1 or −1. If we get −1 then the second equality holds and we are done.
In the case when we've taken out every power of 2 and the second equality never held, we are left with the first equality which also must be equal to 1 or −1, as it too is a square root. However, if the second equality never held, then it couldn't have held for ''r'' = 0, meaning that
:$$
a^{2^0cdot d} = a^d
otequiv -1pmod{n}

Thus in the case the second equality doesn't hold, the first equality must.
The Miller-Rabin primality test is based on the contrapositive of the above claim. That is, if we can find an ''a'' such that
:$$
a^{d}
otequiv 1pmod{n}

and
:$$
a^{2^rd}
otequiv -1pmod{n} for all $0\; le\; r\; le\; s-1$

then ''a'' is a witness for the compositeness of ''n'' (sometimes misleadingly called a ''strong witness'', although it is a certain proof of this fact). Otherwise ''a'' is called a ''strong liar'', and ''n'' is a strong probable prime to base ''a''. The term "strong liar" refers to the case where ''n'' is composite but nevertheless the equations hold as they would for a prime.
For every odd composite ''n'', there are many witnesses ''a''. However, no simple way of generating such an ''a'' is known. The solution is to make the test probabilistic: we choose $a\; in\; left(mathbb\{Z\}/nmathbb\{Z\}$
ight) randomly, and check whether or not it is a witness for the compositeness of ''n''. If ''n'' is composite, most of the ''a''s are witnesses, thus the test will detect ''n'' as composite with high probability. There is nevertheless a small chance that we are unlucky and hit an ''a'' which is a strong liar for ''n''. We may reduce the probability of such error by repeating the test for several independently chosen ''a''.

Example

Suppose we wish to determine if ''n'' = 221 is prime. We write ''n'' − 1 = 220 as 2^''2''·''55'', so that we have ''s'' = 2 and ''d'' = 55. We randomly select an ''a'' < ''n'' of 174. We proceed to compute:

★ ''a''^''d'' mod ''n'' = 174⁵⁵ mod 221 = 47 ≠ 1

★ ''a''^20·''d'' mod ''n'' = 174⁵⁵ mod 221 = 47 ≠ ''n''−1

★ ''a''^21·''d'' mod ''n'' = 174¹¹⁰ mod 221 = 220 = ''n''−1.
Since 220 ≡ -1 mod ''n'', either 221 is prime, or 174 is a strong liar for 221. We try another random ''a'', this time choosing ''a''=137:

★ ''a''^''d'' mod ''n'' = 137⁵⁵ mod 221 = 188 ≠ 1

★ ''a''^20·''d'' mod ''n'' = 137⁵⁵ mod 221 = 188 ≠ ''n''−1

★ ''a''^21·''d'' mod ''n'' = 137¹¹⁰ mod 221 = 205 ≠ ''n''−1.
Hence 137 is a witness for the compositeness of 221, and 174 was in fact a strong liar. Note that this tells us nothing about the factors of 221, which are 13 and 17.

Algorithm and running time

The algorithm can be written as follows:
:'Inputs': $n\; >\; 1$ : an odd integer to test for primality; $k$: a parameter that determines the accuracy of the test
:'Output': composite if $n$ is composite, otherwise probably prime
:write $n\; -\; 1$ as $2^s\; cdot\; d$ by factoring powers of 2 from $n\; -\; 1$
:repeat $k$ times:
::pick $a$ randomly in the range [ $1,\; n\; -\; 1$ ]
::if $a^d$
e 1 mod n and
e -1 for all $r$ in the range $[0,\; s\; -\; 1$] then return composite
:return probably prime
Using modular exponentiation by repeated squaring, the running time of
this algorithm is O(''k'' × log³ ''n''), where ''k''
is the number of different values of ''a'' we test; thus this is an efficient, polynomial-time algorithm. FFT-based multiplication can push the running time down to O(''k'' × log² ''n'' log log ''n'' log log log ''n'') = Õ(''k''
× log² ''n'').

Sample Code

Here is a sample implementation of the algorithm in Ruby
class Integer
def prime?
n = self.abs()
return true if n

2
return false if n

1 || n & 1 == 0
d = n-1
d >>= 1 while d & 1 == 0
20.times do # 20 = k from above
a = rand(n-2) + 1
t = d
y = ModMath.pow(a,t,n) # implemented below
while t != n-1 && y != 1 && y != n-1
y = (y
★ y) % n
t <<= 1
end
return false if y != n-1 && t & 1 == 0
end
return true
end
end
module ModMath
def ModMath.pow(base, power, mod)
result = 1
while power > 0
result = (result
★ base) % mod if power & 1 == 1
base = (base
★ base) % mod
power >>= 1;
end
result
end
end

Accuracy of the test

The more bases ''a'' we test, the better the accuracy of the test. It can be shown that for any odd composite ''n'' always at least 3/4 of the bases ''a'' are witnesses for the compositeness of ''n''. The Miller-Rabin test is strictly stronger than the Solovay-Strassen primality test in the sense that for every composite ''n'', the set of strong liars for ''n'' is a subset of the set of Euler liars for ''n'', and for many ''n'', the subset is proper. If ''n'' is composite then the Miller-Rabin primality test declares ''n'' probably prime with a probability at most $4^\{-k\}$. On the other hand, the Solovay-Strassen primality test declares ''n'' probably prime with a probability at most $2^\{-k\}$.
On average the probability that a composite number is declared probable prime is significantly smaller than $4^\{-k\}$. Damgård, Landrock and Pomerance compute some explicit bounds. Such bounds can for example be used to ''generate'' primes, but should not be used to ''verify'' primes with unknown origin. Especially in cryptographic application an adversary might try to send you a pseudoprime in a place where a prime number is required. Then only the bound $4^\{-k\}$ can be relied upon at this time.

Deterministic variants of the test

The Miller-Rabin algorithm can be made deterministic by trying all possible ''a'' below a certain limit. The problem in general is to set the limit so that the test is still reliable.
If the tested number ''n'' is composite, the strong liars ''a'' coprime to ''n'' are contained in a proper subgroup of the group $left(mathbb\{Z\}/nmathbb\{Z\}$
ight)^
★ , which means that if we test all ''a'' from a set which generates $left(mathbb\{Z\}/nmathbb\{Z\}$
ight)^
★ , one of them must be a witness for the compositeness of ''n''. Assuming the truth of the generalized Riemann hypothesis (GRH), it is known that the group is generated by its elements smaller than O((log ''n'')²), which was already noted by Miller. The constant involved in the Big O notation was reduced to 2 by Eric Bach (1990). This leads to the following conditional primality testing algorithm:
:'Input': ''n'' > 1: an odd integer to test for primality
:'Output': composite if ''n'' is composite, otherwise prime
:write ''n'' − 1 as $2^s\; cdot\; d$ by factoring powers of 2 from ''n'' − 1
:repeat for all ''a'' in the range $[2,min(n-1,lfloor2(ln\; n)^2$
floor)]:
::if ''a''^''d'' mod ''n'' ≠ 1 and $a^\{d\; cdot\; 2^r\}$ mod ''n'' ≠ −1 for all ''r'' in the range [0, ''s'' − 1] then return composite
:return prime
The running time of the algorithm is Õ((log ''n'')⁴). The full power of the generalized Riemann hypothesis is not needed to ensure the correctness of the test: as we deal with subgroups of even index, it suffices to assume the validity of GRH for quadratic Dirichlet characters.
This algorithm is not used in practice, as it is much slower than the randomized version of the Miller-Rabin test. For theoretical purposes, it was superseded by the AKS primality test, which does not rely on unproven assumptions.
When the number ''n'' we want to test is small, trying all ''a'' < 2(ln ''n'')² is not necessary, as much smaller sets of potential witnesses are known to suffice. For example, Jaeschke (1993) has verified that

★ if ''n'' < 9,080,191, it is enough to to test ''a'' = 31 and 73.

★ if ''n'' < 4,759,123,141, it is enough to test ''a'' = 2, 7, and 61.

★ if ''n'' < 2,152,302,898,747, it is enough to test ''a'' = 2, 3, 5, 7, and 11.

★ if ''n'' < 3,474,749,660,383, it is enough to test ''a'' = 2, 3, 5, 7, 11, and 13.

★ if ''n'' < 341,550,071,728,321, it is enough to test ''a'' = 2, 3, 5, 7, 11, 13, and 17.
(Only bases ''a'' < ''n'' should be tested.) See [1] for other criteria of this sort. These results give very fast deterministic primality tests for numbers in the appropriate range, without any assumptions.
Because BPP is contained in P/poly, there is such a small list of potential witnesses for every possible input size (at most ''n'' values for ''n''-bit numbers). However, no finite set of bases is sufficient for all composite numbers.
Alford, Granville and Pomerance have shown that there exist infinitely many composite numbers ''n'' whose smallest compositeness witness is at least $(ln\; n)^\{1/(3lnlnln\; n)\};$. They also argue heuristically that the smallest number ''w'' such that every composite number below ''n'' has a compositeness witness less than ''w'' should be of order $Theta(log\; n,loglog\; n)$.

References

★ W. R. Alford, A. Granville and C. Pomerance, ''On the difficulty of finding reliable witnesses'', in: Algorithmic Number Theory, First International Symposium, Proceedings (L. M. Adleman, M.-D. Huang, eds.), LNCS 877, Springer-Verlag, 1994, pp. 1–16.

★ Eric Bach, ''Explicit bounds for primality testing and related problems'', Mathematics of Computation 55 (1990), no. 191, pp. 355–380.

★ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 890–896 of section 31.8, Primality testing.

★ I. Damgård, P. Landrock and C. Pomerance (1993), ''Average case error estimates for the strong probable prime test'', Math. Comp. 61(203) p.177–194.

★ Gerhard Jaeschke, ''On strong pseudoprimes to several bases'', Mathematics of Computation 61 (1993), no. 204, pp. 915–926.

★ Gary L. Miller, ''Riemann's Hypothesis and Tests for Primality'', Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300–317.

★ Michael O. Rabin, ''Probabilistic algorithm for testing primality'', Journal of Number Theory 12 (1980), no. 1, pp. 128–138.

★ René Schoof, ''Four primality testing algorithms'', to appear in: Surveys in algorithmic number theory, Cambridge University Press. PDF

External links

★ MathWorld - Rabin-Miller Strong Pseudoprime Test

★ The Prime Pages

★ Sierpinski Primes

★ Online Miller-Rabin Primality Test Calculator