Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

Speeding the Pollard and elliptic curve methods of factorization


Author: Peter L. Montgomery
Journal: Math. Comp. 48 (1987), 243-264
MSC: Primary 11Y05; Secondary 11A51, 68Q40
MathSciNet review: 866113
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11A51, 68Q40

Retrieve articles in all journals with MSC: 11Y05, 11A51, 68Q40


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1987-0866113-7
Keywords: Factorization, polynomial evaluation, elliptic curves, Lucas functions
Article copyright: © Copyright 1987 American Mathematical Society