Rolim, José Diaulas Palazzo^{3}, Pardalos, Panos Miltiades^{3}, Reif, John Henry^{3}, Rajasekaran, Sanguthevar^{3}

Affiliations:

^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} unknown^{4} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

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.

ISBN:

0792369579, 9780792369599

Type:

Book chapter

Language:

English

Published in:

Handbook on Randomized Computing: Combinatorial Optimization, Vol. 9, 2001, p. 843-935