Faster deterministic integer factorization
HTML articles powered by AMS MathViewer
- by Edgar Costa and David Harvey PDF
- Math. Comp. 83 (2014), 339-345
Abstract:
The best known unconditional deterministic complexity bound for computing the prime factorization of an integer $N$ is $O(\mathsf {M}_{\mathrm {int}}(N^{1/4} \log N))$, where $\mathsf {M}_{\mathrm {int}}(k)$ denotes the cost of multiplying $k$-bit integers. This result is due to Bostan, Gaudry, and Schost, following the Pollard–Strassen approach. We show that this bound can be improved by a factor of $\sqrt {\log \log N}$.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
- Richard Crandall, Karl Dilcher, and Carl Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), no. 217, 433–449. MR 1372002, DOI 10.1090/S0025-5718-97-00791-6
- Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
- Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
- Niels Möller, On Schönhage’s algorithm and subquadratic integer GCD computation, Math. Comp. 77 (2008), no. 261, 589–607. MR 2353968, DOI 10.1090/S0025-5718-07-02017-0
- 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
- 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
- Arnold Schönhage, Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients, Computer algebra (Marseille, 1982) Lecture Notes in Comput. Sci., vol. 144, Springer, Berlin-New York, 1982, pp. 3–15. MR 680048
- Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
Additional Information
- Edgar Costa
- Affiliation: Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, New York 10012-1185
- MR Author ID: 1041071
- ORCID: 0000-0003-1367-7785
- Email: edgarcosta@nyu.edu
- 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
- Received by editor(s): January 31, 2012
- Received by editor(s) in revised form: April 14, 2012
- Published electronically: May 7, 2013
- Additional Notes: The first author was partially supported by FCT doctoral grant SFRH/BD/69914/2010.
The second author was partially supported by the Australian Research Council, DECRA Grant DE120101293. - © Copyright 2013 by the authors
- Journal: Math. Comp. 83 (2014), 339-345
- MSC (2010): Primary 11Y05
- DOI: https://doi.org/10.1090/S0025-5718-2013-02707-X
- MathSciNet review: 3120593