On Fri, Mar 12, 2010 at 9:13 AM, Russ Cox <[email protected]> wrote: > > In theory this bug could result in false positives, claiming > a number is prime when in fact it is not. In practice, > the smallprimetest eliminates obvious mistakes without > any repetitions, and for random inputs of the size we use > in cryptographic keys, the probability of a single Miller-Rabin > round being wrong is actually more like 1 in 10^80 than > like 1 in 4. Empirically, I've ran both old and new > code side by side for a few million random inputs and > never saw the two differ. Even though we typically try > to use 20 or so rounds for cryptographic keys, that's > intentional overkill. Some texts (e.g., CLR) argue that > three rounds is enough, and some papers suggest that > only the first round has any value. >
This paper has a definitive table of upper bounds for the probability of a k-bit random odd number from a uniformly distribution to pass t iterations of the test: Damgård, I.; Landrock, P.; and Pomerance, C. "Average Case Error Estimates for the Strong Probably Prime Test." Math. Comput. 61, 177-194, 1993. For instance: P(600-bit, 1-iteration) <= 2^-75, which is good, but P(100-bit, 1-iteration) <= 2^-5, so more iterations are really needed here as P(100-bit, 10-iteration) <= 2^-44 As for the code, since you are already doing a Fermat test, you might as well do an iteration with base 2, which takes the same time and gives much stronger result. Also if you do that, you can reduce the (boy, really really long) list of smallprimes to this <http://www.research.att.com/~njas/sequences/A001262>, as the base 2 strong-pseudoprime test will really weeds out composites in a few instructions anyway. -- // aht
