## 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*.

Original language | English |
---|---|

Title of host publication | Handbook on Randomized Computing : Combinatorial Optimization, Vol. 9 |

Number of pages | 92 |

Volume | II, chapter 19 |

Publisher | Kluwer Academic Publishers (Springer) |

Publication date | 2001 |

Edition | chapter 19 |

Pages | 843-935 |

ISBN (Print) | 978-0-7923-6959-9 |

ISBN (Electronic) | 0-7923-6957-9 |

Publication status | Published - 2001 |