Consider a randomized algorithm, such as the Rabin primality test of Rabin, 1976. This algorithm is given as input an integer n, and as auxiliary input, a sequence of coin tosses, i.e., a vector of unbiased independent random bits. The test gives as output either "n is a prime" or "n is not a prime". For every input n, the probability that the output is a false statement is bounded form above by a small constant say ¼.

The test runs in time polynomial in the size of the binary representation of n. In particular, the number r of random bits needed is polynomial in log n.