A time-space tradeoff for Lehman’s deterministic integer factorization method
HTML articles powered by AMS MathViewer
- by Markus Hittmeir;
- Math. Comp. 90 (2021), 1999-2010
- DOI: https://doi.org/10.1090/mcom/3623
- Published electronically: April 13, 2021
- HTML | PDF | Request permission
Abstract:
Fermat’s well-known factorization algorithm is based on finding a representation of natural numbers $N$ as the difference of squares. In 1895, Lawrence generalized this idea and applied it to multiples $kN$ of the original number. A systematic approach to choose suitable values for $k$ was introduced by Lehman in 1974, which resulted in the first deterministic factorization algorithm considerably faster than trial division. In this paper, we construct a time-space tradeoff for Lawrence’s generalization and apply it together with Lehman’s result to obtain a deterministic integer factorization algorithm with runtime complexity $O(N^{2/9+o(1)})$. This is the first exponential improvement since the establishment of the $O(N^{1/4+o(1)})$ bound in 1977.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
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
- D. Harvey and J. van der Hoeven, Integer multiplication in time $O(n \log n)$, hal-02070778, 2019.
- Markus Hittmeir, A babystep-giantstep method for faster deterministic integer factorization, Math. Comp. 87 (2018), no. 314, 2915–2935. MR 3834692, DOI 10.1090/mcom/3313
- F. W. Lawrence, Factorisation of numbers, Messenger of Math. 24 (1895), 100–109.
- R. Sherman Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646. MR 340163, DOI 10.1090/S0025-5718-1974-0340163-2
- 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
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
- 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
- R. Sedgewick, K. Wayne, Algorithms, Princeton University, Fourth Edition, Addison-Wesley, 2011.
- Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
- 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
Bibliographic Information
- Markus Hittmeir
- Affiliation: SBA Research, Floragasse 7, A-1040 Vienna
- MR Author ID: 1220564
- ORCID: 0000-0002-3363-6270
- Email: mhittmeir@sba-research.org
- Received by editor(s): June 30, 2020
- Received by editor(s) in revised form: October 30, 2020, and November 18, 2020
- Published electronically: April 13, 2021
- Additional Notes: SBA Research (SBA-K1) is a COMET Centre within the framework of COMET – Competence Centers for Excellent Technologies Programme and funded by BMK, BMDW, and the federal state of Vienna. The COMET Programme is managed by FFG
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 1999-2010
- MSC (2020): Primary 11Y05
- DOI: https://doi.org/10.1090/mcom/3623
- MathSciNet review: 4273122