Factoring large integers
HTML articles powered by AMS MathViewer
- by R. Sherman Lehman PDF
- Math. Comp. 28 (1974), 637-646 Request permission
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
-
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.
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Math. Comp. 28 (1974), 637-646
- MSC: Primary 10A25
- DOI: https://doi.org/10.1090/S0025-5718-1974-0340163-2
- MathSciNet review: 0340163