Primality testing with fewer random bits

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a number n, the algorithm chooses "candidates"x₁, x₂, ..., 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₂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).