Primality testing with fewer random bits |
| |
Authors: | René Peralta Victor Shoup |
| |
Affiliation: | (1) Computer Science Department, University of Wisconsin-Milwaukee, P. O. Box 784, 53201 Milwaukee, WI, USA;(2) Department of Computer Science, University of Toronto, M5S 1A4 Toronto, Ontario, Canada |
| |
Abstract: | In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a numbern, the algorithm chooses candidatesx
1,x
2, ...,x
k uniformly and independently at random from
n
, and tests if any is a witness to the compositeness ofn. 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 asx, x+1, ..., x+k–1, wherex is chosen uniformly at random from
n
. We prove that fork=1/2log2
n], the error probability of the Miller-Rabin test is no more thann
–1/2+o(1), which improves on the boundn
–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 ofn
–1/2+o(1) if the number of distinct prime factors ofn iso(logn/loglogn). |
| |
Keywords: | primality randomized algorithms derandomization |
本文献已被 SpringerLink 等数据库收录! |
|