Rajasekaran, Sanguthevar3, Pardalos, Panos Miltiades3, Reif, John Henry3, Rolim, José Diaulas Palazzo3
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.
Handbook on Randomized Computing: Combinatorial Optimization, Vol. 9, 2001, p. 843-935