Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Improved error bounds for the Fermat primality test on random inputs


Authors: Jared Duker Lichtman and Carl Pomerance
Journal: Math. Comp. 87 (2018), 2871-2890
MSC (2010): Primary 11Y11; Secondary 11A51
DOI: https://doi.org/10.1090/mcom/3314
Published electronically: February 23, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We investigate the probability that a random odd composite number passes a random Fermat primality test, improving on earlier estimates in moderate ranges. For example, with random numbers to $ 2^{200}$, our results improve on prior estimates by close to 3 orders of magnitude.


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


Similar Articles

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

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


Additional Information

Jared Duker Lichtman
Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755
Email: lichtman.18@dartmouth.edu, jared.d.lichtman@gmail.com

Carl Pomerance
Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755
Email: carl.pomerance@dartmouth.edu

DOI: https://doi.org/10.1090/mcom/3314
Keywords: Fermat test, Miller--Rabin test, probable prime
Received by editor(s): September 13, 2016
Received by editor(s) in revised form: July 5, 2017
Published electronically: February 23, 2018
Additional Notes: The first-named author is grateful for support received from the Byrne Scholars Program and the James O. Freedman Presidential Scholars program at Dartmouth College.
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society