Miller-Rabin primality test
The Miller-Rabin test is a primality test: an algorithm
which determines whether a given number is prime,
similar to the Fermat primality test. Its
original version, due to G. L. Miller, is deterministic, but it relies
on the unproven generalized Riemann hypothesis; M. O. Rabin modified it to
obtain an unconditional probabilistic algorithm.
Suppose n > 1 is an odd integer which we want to test for primality. Write n − 1 = 2k m with m odd and choose a random integer a with 1 < a < n − 1.
If
- <math>a^m \equiv \pm 1 \mod n<math>
or
- <math>a^{2^r m} \equiv -1 \mod n<math>
for at least one r = 1, ..., k−1, then n is declared "probable prime"; if not, then n is definitely composite. (All these powers can be computed quickly with exponentiating by squaring.) If n is found to be a probable prime, another value for a can be chosen and the method repeated, each time reducing the error probability.
It can be proven that a composite number is declared "probable prime" by one round of this algorithm with a probability that is less than 1/4; in fact, in practice the probability is much lower.
Assuming the truth of the generalized Riemann hypothesis, one can prove that, if all the values of a up to 2(ln n)2 have been tested and n is still pronounced a "probable prime", then it is in fact guaranteed to be prime. This leads to a deterministic primality test that has runtime O((ln n)4).
