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

Harvey, David; Hittmeir, Markus

doi:10.1090/mcom/3708

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