Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1993-1189518-9
PII: S 0025-5718(1993)1189518-9
Article copyright: © Copyright 1993 American Mathematical Society