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).
- Subject classifications: 11Y11, 11Y16
- randomized algorithms
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics
- Computational Mathematics