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

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