Remote Access Mathematics of Computation
Green Open Access

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?)

    G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 4th ed., Oxford Univ. Press, London, 1960. 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

Keywords: Factorization, Farey series, minimum operations, Fermat’s method
Article copyright: © Copyright 1974 American Mathematical Society