An exponent one-fifth algorithm for deterministic integer factorisation

Harvey, David

doi:10.1090/mcom/3658

An exponent one-fifth algorithm for deterministic integer factorisation
HTML articles powered by AMS MathViewer

by David Harvey;

Math. Comp. 90 (2021), 2937-2950

DOI: https://doi.org/10.1090/mcom/3658

Published electronically: June 30, 2021

HTML | PDF

Abstract:

Hittmeir recently presented a deterministic algorithm that provably computes the prime factorisation of a positive integer $N$ in $N^{2/9+o(1)}$ bit operations. Prior to this breakthrough, the best known complexity bound for this problem was $N^{1/4+o(1)}$, a result going back to the 1970s. In this paper we push Hittmeir’s techniques further, obtaining a rigorous, deterministic factoring algorithm with complexity $N^{1/5+o(1)}$.

References

Daniel J. Bernstein, Reducing lattice bases to find small-height values of univariate polynomials, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 421–446. MR 2467553
F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, and P. Zimmermann, Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment, Cryptology ePrint Archive, Report 2020/697, 2020, https://eprint.iacr.org/2020/697.
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
Don Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), no. 4, 233–260. MR 1476612, DOI 10.1007/s001459900030
Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
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
M. Hittmeir, A time-space tradeoff for Lehman’s deterministic integer factorization method, to appear in Mathematics of Computation; arXiv preprint, http://arxiv.org/abs/2006.16729v1, 2020.
David Harvey and Joris van der Hoeven, On the complexity of integer matrix multiplication, J. Symbolic Comput. 89 (2018), 1–8. MR 3804803, DOI 10.1016/j.jsc.2017.11.001
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
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 6th ed., Oxford University Press, Oxford, 2008. Revised by D. R. Heath-Brown and J. H. Silverman; With a foreword by Andrew Wiles. MR 2445243
Donald E. Knuth, The art of computer programming. Vol. 3, Addison-Wesley, Reading, MA, 1998. Sorting and searching; Second edition [of MR0445948]. MR 3077154
R. Sherman Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646. MR 340163, DOI 10.1090/S0025-5718-1974-0340163-2
H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483–516. MR 1137100, DOI 10.1090/S0894-0347-1992-1137100-0
James McKee and Richard Pinch, Old and new deterministic factoring algorithms, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 217–224. MR 1446514, DOI 10.1007/3-540-61581-4_{5}7
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Proc. Sympos. Pure Math., Vol. XX, Amer. Math. Soc., Providence, RI, 1971, pp. 415–440. MR 316385
Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994) IEEE Comput. Soc. Press, Los Alamitos, CA, 1994, pp. 124–134. MR 1489242, DOI 10.1109/SFCS.1994.365700
Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 3rd ed., Cambridge University Press, Cambridge, 2013. MR 3087522, DOI 10.1017/CBO9781139856065