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
DOI: https://doi.org/10.1090/mcom/3313
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
Email: m.hittmeir@hotmail.com

DOI: https://doi.org/10.1090/mcom/3313
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