Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



A deterministic algorithm for integer factorization

Author: Ghaith A. Hiary
Journal: Math. Comp. 85 (2016), 2065-2069
MSC (2010): Primary 11Y05
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

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

American Mathematical Society