Miller-Rabin primality test

The Miller-Rabin test is a primality test: an algorithm which determines whether a given number is prime. Its original version is probabilistic and similar to the Fermat primality test.

Suppose n > 1 is an odd integer which we want to test for primality. Write n - 1 = 2^k 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))² 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)⁴).