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
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 $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?)

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1989 American Mathematical Society