Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ n \leq x$, (2) chooses a random number b, $ 1 < b < n - 1$, and (3) accepts n if $ {b^{n - 1}} \equiv 1\;\pmod n$. Let $ P(x)$ denote the probability that this procedure accepts a composite number. It is known from work of Erdös and the second author that $ P(x) \to 0$ as $ x \to \infty $. In this paper, explicit inequalities are established for $ P(x)$. For example, it is shown that $ P({10^{100}}) < 2.77 \times {10^{ - 8}}$ and that $ P(x) \leq {(\log x)^{ - 197}}$ for $ x \geq {10^{{{10}^5}}}$.


References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society