ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# 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 = 2k m with m odd and choose a random integer a with 1 < a < n - 1.

If

or
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).

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.