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.


Speeding the Pollard and elliptic curve methods of factorization
HTML articles powered by AMS MathViewer

by Peter L. Montgomery PDF
Math. Comp. 48 (1987), 243-264 Request permission


Since 1974, several algorithms have been developed that attempt to factor a large number N by doing extensive computations modulo N and occasionally taking GCDs with N. These began with Pollard’s $p - 1$ and Monte Carlo methods. More recently, Williams published a $p + 1$ method, and Lenstra discovered an elliptic curve method (ECM). We present ways to speed all of these. One improvement uses two tables during the second phases of $p \pm 1$ and ECM, looking for a match. Polynomial preconditioning lets us search a fixed table of size n with $n/2 + o(n)$ multiplications. A parametrization of elliptic curves lets Step 1 of ECM compute the x-coordinate of nP from that of P in about 9.3 ${\log _2}$ n multiplications for arbitrary P.
Similar Articles
Additional Information
  • © Copyright 1987 American Mathematical Society
  • Journal: Math. Comp. 48 (1987), 243-264
  • MSC: Primary 11Y05; Secondary 11A51, 68Q40
  • DOI:
  • MathSciNet review: 866113