Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Average case error estimates for the strong probable prime test

Authors: Ivan Damgård, Peter Landrock and Carl Pomerance
Journal: Math. Comp. 61 (1993), 177-194
MSC: Primary 11Y11; Secondary 11A51
MathSciNet review: 1189518
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Consider a procedure that chooses k-bit odd numbers independently and from the uniform distribution, subjects each number to t independent iterations of the strong probable prime test (Miller-Rabin test) with randomly chosen bases, and outputs the first number found that passes all t tests. Let $ {p_{k,t}}$ denote the probability that this procedure returns a composite number. We obtain numerical upper bounds for $ {p_{k,t}}$ for various choices of k, t and obtain clean explicit functions that bound $ {p_{k,t}}$ for certain infinite classes of k, t. For example, we show $ {p_{100,10}} \leq {2^{ - 44}},{p_{300,5}} \leq {2^{ - 60}},{p_{600,1}} \leq {2^{ - 75}}$ , and $ {p_{k,1}} \leq {k^2}{4^{2 - \sqrt k }}$ for all $ k \geq 2$. In addition, we characterize the worst-case numbers with unusually many "false witnesses" and give an upper bound on their distribution that is probably close to best possible.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y11, 11A51

Retrieve articles in all journals with MSC: 11Y11, 11A51

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society