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

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?)

  • [1] R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391-1417. MR 583518 (81j:10005)
  • [2] P. Beuchemin, G. Brassard, C. Crépeau, C. Goutier, and C. Pomerance, The generation of random numbers that are probably prime, J. Cryptology 1 (1988), 53-64. MR 935901 (89g:11126)
  • [3] P. Erdös and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259-279. MR 815848 (87i:11183)
  • [4] S. H. Kim and C. Pomerance, The probability that a random probable prime is composite, Math. Comp. 53 (1989), 721-741. MR 982368 (90e:11190)
  • [5] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), 97-108. MR 582244 (82a:68078)
  • [6] C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to $ 25 \cdot {10^9}$, Math. Comp. 35 (1980), 1003-1026. MR 572872 (82g:10030)
  • [7] M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), 128-138. MR 566880 (81f:10003)
  • [8] L. Schoenfeld, Sharpe. bounds for the Chebyshev functions $ \theta (x)$ and $ \psi (x)$. II, Math. Comp. 30 (1976), 337-360; Corrigendum, op cit, 900. MR 0457374 (56:15581b)

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

American Mathematical Society