Skip to Main Content

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 composite
HTML articles powered by AMS MathViewer

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


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}}}$.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 11Y11, 11A51
  • Retrieve articles in all journals with MSC: 11Y11, 11A51
Additional Information
  • © Copyright 1989 American Mathematical Society
  • Journal: Math. Comp. 53 (1989), 721-741
  • MSC: Primary 11Y11; Secondary 11A51
  • DOI:
  • MathSciNet review: 982368