A deterministic algorithm for integer factorization
HTML articles powered by AMS MathViewer
- by Ghaith A. Hiary PDF
- Math. Comp. 85 (2016), 2065-2069 Request permission
Abstract:
A deterministic algorithm for factoring $n$ using $n^{1/3+o(1)}$ bit operations is presented. The algorithm tests the divisibility of $n$ by all the integers in a short interval at once rather than integer by integer as in trial division. The algorithm is implemented.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
- Don Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in cryptology—EUROCRYPT ’96 (Saragossa, 1996) Lecture Notes in Comput. Sci., vol. 1070, Springer, Berlin, 1996, pp. 178–189. MR 1421585, DOI 10.1007/3-540-68339-9_{1}6
- 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
- H. Davenport, The higher arithmetic, 8th ed., Cambridge University Press, Cambridge, 2008. An introduction to the theory of numbers; With editing and additional material by James H. Davenport. MR 2462408, DOI 10.1017/CBO9780511818097
- 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., Divisors in residue classes, Math. Comp. 42 (1984), no. 165, 331–340. MR 726007, DOI 10.1090/S0025-5718-1984-0726007-1
- James McKee, Turning Euler’s factoring method into a factoring algorithm, Bull. London Math. Soc. 28 (1996), no. 4, 351–355. MR 1384821, DOI 10.1112/blms/28.4.351
- J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
- Ronald L. Rivest and Adi Shamir, Efficient factoring based on partial information, Advances in cryptology—EUROCRYPT ’85 (Linz, 1985) Lecture Notes in Comput. Sci., vol. 219, Springer, Berlin, 1986, pp. 31–34. MR 851581, DOI 10.1007/3-540-39805-8_{3}
- Michael O. Rubinstein, The distribution of solutions to $xy=n\pmod a$ with an application to factoring integers, Integers 13 (2013), Paper No. A12, 20. MR 3083474
- Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1–8. MR 438807
- O. N. Vasilenko, Number-theoretic algorithms in cryptography, Translations of Mathematical Monographs, vol. 232, American Mathematical Society, Providence, RI, 2007. Translated from the 2003 Russian original by Alex Martsinkovsky. MR 2273200, DOI 10.1090/mmono/232
Additional Information
- Ghaith A. Hiary
- Affiliation: Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, Ohio 43210
- MR Author ID: 930454
- Email: hiaryg@gmail.com
- Received by editor(s): September 4, 2014
- Received by editor(s) in revised form: December 17, 2014
- Published electronically: October 20, 2015
- Additional Notes: Preparation of this material was partially supported by the National Science Foundation under agreements No. DMS-1406190 and by the Leverhulme Trust (while at the University of Bristol).
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 2065-2069
- MSC (2010): Primary 11Y05
- DOI: https://doi.org/10.1090/mcom3037
- MathSciNet review: 3471119