A babystep-giantstep method for faster deterministic integer factorization

Hittmeir, Markus

doi:10.1090/mcom/3313

A babystep-giantstep method for faster deterministic integer factorization
HTML articles powered by AMS MathViewer

by Markus Hittmeir PDF

Math. Comp. 87 (2018), 2915-2935 Request permission

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 \[ \widetilde {O}\left (N^{1/4}\exp (-C\log N/\log \log N)\right ). \]

References

Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput. 36 (2007), no. 6, 1777–1806. MR 2299425, DOI 10.1137/S0097539704443793
Edgar Costa and David Harvey, Faster deterministic integer factorization, Math. Comp. 83 (2014), no. 285, 339–345. MR 3120593, DOI 10.1090/S0025-5718-2013-02707-X
Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
David Harvey, Joris van der Hoeven, and Grégoire Lecerf, Even faster integer multiplication, J. Complexity 36 (2016), 1–30. MR 3530637, DOI 10.1016/j.jco.2016.03.001
Markus Hittmeir, Deterministic factorization of sums and differences of powers, Math. Comp. 86 (2017), no. 308, 2947–2954. MR 3667032, DOI 10.1090/mcom/3197
Arjen K. Lenstra, Integer factoring, Des. Codes Cryptogr. 19 (2000), no. 2-3, 101–128. Towards a quarter-century of public key cryptography. MR 1758972, DOI 10.1023/A:1008397921377
Hans Riesel, Prime numbers and computer methods for factorization, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1292250, DOI 10.1007/978-1-4612-0251-6
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Lowell Schoenfeld, Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$. II, Math. Comp. 30 (1976), no. 134, 337–360. MR 457374, DOI 10.1090/S0025-5718-1976-0457374-X
Robert Sedgewick, Algorithms, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. MR 784432
Victor Shoup, A computational introduction to number theory and algebra, Cambridge University Press, Cambridge, 2005. MR 2151586, DOI 10.1017/CBO9781139165464
Igor E. Shparlinski, Modular hyperbolas, Jpn. J. Math. 7 (2012), no. 2, 235–294. MR 2995230, DOI 10.1007/s11537-012-1140-8
Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
Andrew V. Sutherland, Order computations in generic groups, ProQuest LLC, Ann Arbor, MI, 2007. Thesis (Ph.D.)–Massachusetts Institute of Technology. MR 2717420
Samuel S. Wagstaff Jr., The joy of factoring, Student Mathematical Library, vol. 68, American Mathematical Society, Providence, RI, 2013. MR 3135977, DOI 10.1090/stml/068