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 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]**Robert Baillie and Samuel S. Wagstaff Jr.,*Lucas pseudoprimes*, Math. Comp.**35**(1980), no. 152, 1391–1417. MR**583518**, 10.1090/S0025-5718-1980-0583518-6**[2]**Pierre Beauchemin, Gilles Brassard, Claude Crépeau, Claude Goutier, and Carl Pomerance,*The generation of random numbers that are probably prime*, J. Cryptology**1**(1988), no. 1, 53–64. MR**935901**, 10.1007/BF00206325**[3]**Paul Erdős and Carl Pomerance,*On the number of false witnesses for a composite number*, Math. Comp.**46**(1986), no. 173, 259–279. MR**815848**, 10.1090/S0025-5718-1986-0815848-X**[4]**Su Hee Kim and Carl Pomerance,*The probability that a random probable prime is composite*, Math. Comp.**53**(1989), no. 188, 721–741. MR**982368**, 10.1090/S0025-5718-1989-0982368-4**[5]**Louis Monier,*Evaluation and comparison of two efficient probabilistic primality testing algorithms*, Theoret. Comput. Sci.**12**(1980), no. 1, 97–108. MR**582244**, 10.1016/0304-3975(80)90007-9**[6]**Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr.,*The pseudoprimes to 25⋅10⁹*, Math. Comp.**35**(1980), no. 151, 1003–1026. MR**572872**, 10.1090/S0025-5718-1980-0572872-7**[7]**Michael O. Rabin,*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, 10.1016/0022-314X(80)90084-0**[8]**Lowell Schoenfeld,*Sharper bounds for the Chebyshev functions 𝜃(𝑥) and 𝜓(𝑥). II*, Math. Comp.**30**(1976), no. 134, 337–360. MR**0457374**, 10.1090/S0025-5718-1976-0457374-X

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