Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Factoring large integers
HTML articles powered by AMS MathViewer

by R. Sherman Lehman PDF
Math. Comp. 28 (1974), 637-646 Request permission


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.
    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
  • © Copyright 1974 American Mathematical Society
  • Journal: Math. Comp. 28 (1974), 637-646
  • MSC: Primary 10A25
  • DOI:
  • MathSciNet review: 0340163