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