## Abstract

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a number n, the algorithm chooses "candidates"x_{1}, x_{2}, ..., x_{k} uniformly and independently at random from ℤ_{n}, and tests if any is a "witness" to the compositeness of n. For either algorithm, the probabilty that it errs is at most 2^{-k}. In this paper, we study the error probabilities of these algorithms when the candidates are instead chosen as x, x+1, ..., x+k-1, where x is chosen uniformly at random from ℤ_{n}. We prove that for k=[1/2log_{2}n], the error probability of the Miller-Rabin test is no more than n^{-1/2+o(1)}, which improves on the bound n^{-1/4+o(1)} previously obtained by Bach. We prove similar bounds for the Solovay-Strassen test, but they are not quite as strong; in particular, we only obtain a bound of n^{-1/2+o(1)} if the number of distinct prime factors of n is o(log n/loglog n).

Original language | English (US) |
---|---|

Pages (from-to) | 355-367 |

Number of pages | 13 |

Journal | Computational Complexity |

Volume | 3 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1993 |

## Keywords

- Subject classifications: 11Y11, 11Y16
- derandomization
- primality
- randomized algorithms

## ASJC Scopus subject areas

- Theoretical Computer Science
- Mathematics(all)
- Computational Theory and Mathematics
- Computational Mathematics