Rolim, José Diaulas Palazzo3, Pardalos, Panos Miltiades3, Reif, John Henry3, Rajasekaran, Sanguthevar3
1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 unknown4 Department of Computer Science, Science and Technology, Aarhus University
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