The probability that a random probable prime is composite

Authors:
Su Hee Kim and Carl Pomerance

Journal:
Math. Comp. **53** (1989), 721-741

MSC:
Primary 11Y11; Secondary 11A51

MathSciNet review:
982368

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Consider a procedure which (1) chooses a random odd number , (2) chooses a random number *b*, , and (3) accepts *n* if . Let denote the probability that this procedure accepts a composite number. It is known from work of Erdös and the second author that as . In this paper, explicit inequalities are established for . For example, it is shown that and that for .

**[1]**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**[2]**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**[3]**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**[4]**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**[5]**J. Barkley Rosser and Lowell Schoenfeld,*Approximate formulas for some functions of prime numbers*, Illinois J. Math.**6**(1962), 64–94. MR**0137689**

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-1989-0982368-4

Article copyright:
© Copyright 1989
American Mathematical Society