# Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

## The probability that a random probable prime is compositeHTML articles powered by AMS MathViewer

by Su Hee Kim and Carl Pomerance
Math. Comp. 53 (1989), 721-741 Request permission

## 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
Similar Articles
• Retrieve articles in Mathematics of Computation with MSC: 11Y11, 11A51
• Retrieve articles in all journals with MSC: 11Y11, 11A51