Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

A deterministic algorithm for integer factorization


Author: Ghaith A. Hiary
Journal: Math. Comp. 85 (2016), 2065-2069
MSC (2010): Primary 11Y05
DOI: https://doi.org/10.1090/mcom3037
Published electronically: October 20, 2015
MathSciNet review: 3471119
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A deterministic algorithm for factoring $ n$ using $ n^{1/3+o(1)}$ bit operations is presented. The algorithm tests the divisibility of $ n$ by all the integers in a short interval at once rather than integer by integer as in trial division. The algorithm is implemented.


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


Similar Articles

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

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


Additional Information

Ghaith A. Hiary
Affiliation: Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, Ohio 43210
Email: hiaryg@gmail.com

DOI: https://doi.org/10.1090/mcom3037
Keywords: Integer factorization, algorithm, continued fraction
Received by editor(s): September 4, 2014
Received by editor(s) in revised form: December 17, 2014
Published electronically: October 20, 2015
Additional Notes: Preparation of this material was partially supported by the National Science Foundation under agreements No. DMS-1406190 and by the Leverhulme Trust (while at the University of Bristol).
Article copyright: © Copyright 2015 American Mathematical Society