Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Mathematics of Computation
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

PII: S 0025-5718(1989)0982368-4
Article copyright: © Copyright 1989 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia