Primality testing with fewer random bits

René Peralta, Victor Shoup

Research output: Contribution to journalArticle

Abstract

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a number n, the algorithm chooses "candidates"x1, x2, ..., xk 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/2log2n], 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 languageEnglish (US)
Pages (from-to)355-367
Number of pages13
JournalComputational Complexity
Volume3
Issue number4
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Primality testing with fewer random bits'. Together they form a unique fingerprint.

  • Cite this