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

DOI:
https://doi.org/10.1090/S0025-5718-1993-1189518-9

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 denote the probability that this procedure returns a composite number. We obtain numerical upper bounds for for various choices of *k, t* and obtain clean explicit functions that bound for certain infinite classes of *k, t*. For example, we show , and for all . 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.

**[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*, 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**and*. II, Math. Comp.**30**(1976), 337-360; Corrigendum, op cit, 900. MR**0457374 (56:15581b)**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1189518-9

Article copyright:
© Copyright 1993
American Mathematical Society