Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



A babystep-giantstep method for faster deterministic integer factorization

Author: Markus Hittmeir
Journal: Math. Comp. 87 (2018), 2915-2935
MSC (2010): Primary 11A51
Published electronically: March 26, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In 1977, Strassen presented a deterministic and rigorous algorithm for solving the problem of computing the prime factorization of natural numbers $ N$. His method is based on fast polynomial arithmetic techniques and runs in time $ \widetilde {O}(N^{1/4})$, which has been state of the art for the last forty years. In this paper, we will combine Strassen's approach with a babystep-giantstep method to improve the currently best known bound by a superpolynomial factor. The runtime complexity of our algorithm is of the form

$\displaystyle \widetilde {O}\left (N^{1/4}\exp (-C\log N/\log \log N)\right ). $

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

Similar Articles

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

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

Additional Information

Markus Hittmeir
Affiliation: Department of Mathematics, University of Salzburg, Hellbrunnerstraße 34, A-5020 Salzburg, Austria

Received by editor(s): August 31, 2016
Received by editor(s) in revised form: September 1, 2016, October 31, 2016, March 6, 2017, May 2, 2017, and July 6, 2017
Published electronically: March 26, 2018
Additional Notes: The author is supported by the Austrian Science Fund (FWF): Project F5504-N26, which is a part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society