Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A deterministic algorithm for integer factorization


Author: Ghaith A. Hiary
Journal: Math. Comp. 85 (2016), 2065-2069
MSC (2010): Primary 11Y05
DOI: https://doi.org/10.1090/mcom3037
Published electronically: October 20, 2015
MathSciNet review: 3471119
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2008a:11156), https://doi.org/10.1137/S0097539704443793
  • [2] 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 (97h:94009), https://doi.org/10.1007/3-540-68339-9_16
  • [3] Edgar Costa and David Harvey, Faster deterministic integer factorization, Math. Comp. 83 (2014), no. 285, 339-345. MR 3120593, https://doi.org/10.1090/S0025-5718-2013-02707-X
  • [4] Richard Crandall and Carl Pomerance, Prime Numbers, A Computational Perspective, 2nd ed., Springer, New York, 2005. MR 2156291 (2006a:11005)
  • [5] H. Davenport, The Higher Arithmetic, An Introduction to the Theory of Numbers,, 8th ed., with editing and additional material by James H. Davenport, Cambridge University Press, Cambridge, 2008. MR 2462408 (2009j:11001)
  • [6] R. Sherman Lehman, Factoring large integers, Math. Comp. 28 (1974), 637-646. MR 0340163 (49 #4919)
  • [7] H. W. Lenstra Jr., Divisors in residue classes, Math. Comp. 42 (1984), no. 165, 331-340. MR 726007 (85b:11118), https://doi.org/10.2307/2007582
  • [8] James McKee, Turning Euler's factoring method into a factoring algorithm, Bull. London Math. Soc. 28 (1996), no. 4, 351-355. MR 1384821 (97f:11010), https://doi.org/10.1112/blms/28.4.351
  • [9] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521-528. MR 0354514 (50 #6992)
  • [10] 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, https://doi.org/10.1007/3-540-39805-8_3
  • [11] 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 pp.. MR 3083474
  • [12] Volker Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), no. 1, 1-8. MR 0438807 (55 #11713)
  • [13] O. N. Vasilenko, Number-theoretic Algorithms in Cryptography, translated from the 2003 Russian original by Alex Martsinkovsky, Translations of Mathematical Monographs, vol. 232, American Mathematical Society, Providence, RI, 2007. MR 2273200 (2007g:11160)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y05

Retrieve articles in all journals with MSC (2010): 11Y05


Additional Information

Ghaith A. Hiary
Affiliation: Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, Ohio 43210
Email: hiaryg@gmail.com

DOI: https://doi.org/10.1090/mcom3037
Keywords: Integer factorization, algorithm, continued fraction
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).
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society