Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

Factoring large integers


Author: R. Sherman Lehman
Journal: Math. Comp. 28 (1974), 637-646
MSC: Primary 10A25
MathSciNet review: 0340163
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A modification of Fermat's difference of squares method is used for factoring large integers. This modification permits factoring n in $ O({n^{1/3}})$ elementary operations, where addition, subtraction, multiplication, division, or the extraction of a square root is considered as an elementary operation. A principal part is played by the use of a dissection of the continuum similar to the Farey dissection. This has been programmed for $ n \leqq 1.05 \times {10^{20}}$ on the CDC 6400.


References [Enhancements On Off] (What's this?)

  • [1] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 4th ed., Oxford Univ. Press, London, 1960.
  • [2] F. W. Lawrence, "Factorisation of numbers," Messenger of Math., v. 24, 1895, pp. 100-109.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A25

Retrieve articles in all journals with MSC: 10A25


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1974-0340163-2
PII: S 0025-5718(1974)0340163-2
Keywords: Factorization, Farey series, minimum operations, Fermat's method
Article copyright: © Copyright 1974 American Mathematical Society