Miller-Rabin primality test
From Wikipedia, the free encyclopedia
|
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.
ConceptsJust 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{Z}/p\mathbb{Z} , where p is prime and Failed to parse (Missing texvc executable; please see math/README to configure.): p > 2 . 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 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:
Since x is not 1 or -1 mod p, both Failed to parse (Missing texvc executable; please see math/README to configure.): x-1 and Failed to parse (Missing texvc executable; please see math/README to configure.): x+1 are co-prime to Failed to parse (Missing texvc executable; please see math/README to configure.): p . Hence, neither Failed to parse (Missing texvc executable; please see math/README to configure.): x-1 nor Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 2^s \cdot d , where s is an integer and d is odd. For each Failed to parse (Missing texvc executable; please see math/README to configure.): a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^* , either
or
for some Failed to parse (Missing texvc executable; please see math/README to configure.): 0 \le r \le s-1
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
The Miller-Rabin primality test is based on the contrapositive of the above claim. That is, if we can find an a such that
and
for all Failed to parse (Missing texvc executable; please see math/README to configure.): 0 \le r \le s-1
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 Failed to parse (Missing texvc executable; please see math/README to configure.): a \in \left(\mathbb{Z}/n\mathbb{Z}\right) randomly, and check whether or not it is a witness for the compositeness of n. If n is composite, most of the as 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. ExampleSuppose we wish to determine if n = 221 is prime. We write n − 1 = 220 as 22·55, so that we have s = 2 and d = 55. We randomly select an a < n of 174. We proceed to compute:
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:
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 timeThe algorithm can be written as follows:
: an odd integer to test for primality; Failed to parse (Missing texvc executable; please see math/README to configure.): k
is composite, otherwise probably prime
as Failed to parse (Missing texvc executable; please see math/README to configure.): 2^s \cdot d by factoring powers of 2 from Failed to parse (Missing texvc executable; please see math/README to configure.): n - 1
times:
randomly in the range [ Failed to parse (Missing texvc executable; please see math/README to configure.): 1, n - 1\ ]
and Failed to parse (Missing texvc executable; please see math/README to configure.): a^{{2^r}d}\ \not\equiv -1 \bmod\ n
for all Failed to parse (Missing texvc executable; please see math/README to configure.): r
in the range Failed to parse (Missing texvc executable; please see math/README to configure.): [0, s - 1\
] then return composite
Using modular exponentiation by repeated squaring, the running time of this algorithm is O(k × log3 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 × log2 n log log n log log log n) = Õ(k × log2 n). Sample CodeHere is a sample implementation of the algorithm in Ruby <source lang="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
</source> Accuracy of the testThe 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 4^{-k} . On the other hand, the Solovay-Strassen primality test declares n probably prime with a probability at most Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{-k} . On average the probability that a composite number is declared probable prime is significantly smaller than Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 4^{-k} can be relied upon at this time. Deterministic variants of the testThe 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \left(\mathbb{Z}/n\mathbb{Z}\right)^* , which means that if we test all a from a set which generates Failed to parse (Missing texvc executable; please see math/README to configure.): \left(\mathbb{Z}/n\mathbb{Z}\right)^* , 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)2), 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:
by factoring powers of 2 from n − 1
mod n ≠ −1 for all r in the range [0, s − 1] then return composite
The running time of the algorithm is Õ((log n)4). 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)2 is not necessary, as much smaller sets of potential witnesses are known to suffice. For example, Jaeschke (1993) has verified that
(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 Failed to parse (Missing texvc executable; please see math/README to configure.): (\ln n)^{1/(3\ln\ln\ln 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \Theta(\log n\,\log\log n) . References
External links
es:Test de primalidad de Miller-Rabin fr:Test de primalité de Miller-Rabin ko:밀러-라빈 소수판별법 it:Test di Miller-Rabin he:אלגוריתם מילר-רבין ja:ミラー-ラビン素数判定法 pl:Test Millera-Rabina pt:Teste de primitividade de Miller-Rabin ru:Тест Миллера — Рабина vi:Kiểm tra Miller-Rabin | ||||||||||||||
