Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

Counting composites with two strong liars


Authors: Eric Bach and Andrew Shallue
Journal: Math. Comp. 84 (2015), 3069-3089
MSC (2010): Primary 11Y11
Published electronically: April 1, 2015
MathSciNet review: 3378863
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The strong probable primality test is an important practical tool for discovering prime numbers. Its effectiveness derives from the following fact: for any odd composite number $ n$, if a base $ a$ is chosen at random, the algorithm is unlikely to claim that $ n$ is prime. If this does happen we call $ a$ a liar. In 1986, Erdős and Pomerance computed the normal and average number of liars, over all $ n \leq x$. We continue this theme and use a variety of techniques to count $ n \leq x$ with exactly two strong liars, those being the $ n$ for which the strong test is maximally effective. We evaluate this count asymptotically and give an improved algorithm to determine it exactly. We also provide asymptotic counts for the restricted case in which $ n$ has two prime factors, and for the $ n$ with exactly two Euler liars.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y11

Retrieve articles in all journals with MSC (2010): 11Y11


Additional Information

Eric Bach
Affiliation: University of Wisconsin–Madison, 1210 W. Dayton St., Madison, Wisconsin 53706
Email: bach@cs.wisc.edu

Andrew Shallue
Affiliation: Illinois Wesleyan University, 1312 Park St., Bloomington, Illinois 61701
Email: ashallue@iwu.edu

DOI: https://doi.org/10.1090/mcom/2949
Received by editor(s): August 4, 2013
Received by editor(s) in revised form: February 16, 2014
Published electronically: April 1, 2015
Additional Notes: This research supported by NSF: CCF-0635355 and ARO: W911NF9010439
Article copyright: © Copyright 2015 American Mathematical Society