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

DOI:
https://doi.org/10.1090/S0025-5718-1989-0982368-4

MathSciNet review:
982368

Full-text PDF

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]**P. Beauchemin, G. Brassard, C. Crépeau, C. Goutier & C. Pomerance, "The generation of random numbers that are probably prime,"*J. Cryptology*, v. 1, 1988, pp. 53-64. MR**935901 (89g:11126)****[2]**P. Erdös & C. Pomerance, "On the number of false witnesses for a composite number,"*Math. Comp.*, v. 46, 1986, pp. 259-279. MR**815848 (87i:11183)****[3]**L. Monier, "Evaluation and comparison of two efficient probabilistic primality testing algorithms,"*Theoret. Comput. Sci.*, v. 12, 1980, pp. 97-108. MR**582244 (82a:68078)****[4]**M. O. Rabin, "Probabilistic algorithm for testing primality,"*J. Number Theory*, v. 12, 1980, pp. 128-138. MR**566880 (81f:10003)****[5]**J. B. Rosser & L. Schoenfeld, "Approximate formulas for some functions of prime numbers,"*Illinois J. Math.*, v. 6, 1962, pp. 64-94. MR**0137689 (25:1139)**

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

Article copyright:
© Copyright 1989
American Mathematical Society