## A log-log speedup for exponent one-fifth deterministic integer factorisation

HTML articles powered by AMS MathViewer

- by
David Harvey and Markus Hittmeir
**HTML**| PDF - Math. Comp.
**91**(2022), 1367-1379 Request permission

## Abstract:

Building on techniques recently introduced by the second author, and further developed by the first author, we show that a positive integer $N$ may be rigorously and deterministically factored into primes in at most \[ O\left ( \frac {N^{1/5} \log ^{16/5} N}{(\log \log N)^{3/5}}\right ) \] bit operations. This improves on the previous best known result by a factor of $(\log \log N)^{3/5}$.## 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 - L. I. Bluestein,
*A linear filtering approach to the computation of discrete Fourier transform*, IEEE Transactions on Audio and Electroacoustics**18**(1970), no. 4, 451–455. - Richard P. Brent and Paul Zimmermann,
*Modern computer arithmetic*, Cambridge Monographs on Applied and Computational Mathematics, vol. 18, Cambridge University Press, Cambridge, 2011. MR**2760886** - 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 - Richard Crandall and Carl Pomerance,
*Prime numbers*, 2nd ed., Springer, New York, 2005. A computational perspective. MR**2156291** - Steven D. Galbraith,
*Mathematics of public key cryptography*, Cambridge University Press, Cambridge, 2012. MR**2931758**, DOI 10.1017/CBO9781139012843 - David Harvey,
*An exponent one-fifth algorithm for deterministic integer factorisation*, Math. Comp.**90**(2021), no. 332, 2937–2950. MR**4305375**, DOI 10.1090/mcom/3658 - Ghaith A. Hiary,
*A deterministic algorithm for integer factorization*, Math. Comp.**85**(2016), no. 300, 2065–2069. MR**3471119**, DOI 10.1090/mcom3037 - 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 - Markus Hittmeir,
*A time-space tradeoff for Lehman’s deterministic integer factorization method*, Math. Comp.**90**(2021), no. 330, 1999–2010. MR**4273122**, DOI 10.1090/mcom/3623 - David Harvey and Joris van der Hoeven,
*Integer multiplication in time $O(n \log n)$*, Ann. of Math. (2)**193**(2021), no. 2, 563–617. MR**4224716**, DOI 10.4007/annals.2021.193.2.4 - Donald E. Knuth,
*The art of computer programming. Vol. 3*, Addison-Wesley, Reading, MA, 1998. Sorting and searching; Second edition [of MR0445948]. MR**3077154** - Michael Kaib and Claus P. Schnorr,
*The generalized Gauss reduction algorithm*, J. Algorithms**21**(1996), no. 3, 565–578. MR**1417664**, DOI 10.1006/jagm.1996.0059 - Serge Lang,
*Algebraic number theory*, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR**1282723**, DOI 10.1007/978-1-4612-0853-2 - 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 - Hugh L. Montgomery and Robert C. Vaughan,
*Multiplicative number theory. I. Classical theory*, Cambridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007. MR**2378655** - Andrew Novocin, Damien Stehlé, and Gilles Villard,
*An LLL-reduction algorithm with quasi-linear time complexity [extended abstract]*, STOC’11—Proceedings of the 43rd ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 403–412. MR**2931990**, DOI 10.1145/1993636.1993691 - 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 - Joachim von zur Gathen and Jürgen Gerhard,
*Modern computer algebra*, 3rd ed., Cambridge University Press, Cambridge, 2013. MR**3087522**, DOI 10.1017/CBO9781139856065 - 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

## Additional Information

**David Harvey**- Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
- MR Author ID: 734771
- ORCID: 0000-0002-4933-658X
- Email: d.harvey@unsw.edu.au
**Markus Hittmeir**- Affiliation: SBA Research, Floragasse 7, A-1040 Vienna, Austria
- MR Author ID: 1220564
- ORCID: 0000-0002-3363-6270
- Email: mhittmeir@sba-research.org
- Received by editor(s): June 8, 2021
- Received by editor(s) in revised form: October 12, 2021
- Published electronically: December 15, 2021
- Additional Notes: Dedicated to Richard Brent on the occasion of his $(3 \times 5^2)$-th birthday

The first author was supported by the Australian Research Council (grant FT160100219).

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.
**91**(2022), 1367-1379 - MSC (2020): Primary 11Y05
- DOI: https://doi.org/10.1090/mcom/3708
- MathSciNet review: 4405498