Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Mathematics of Computation
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

PII: S 0025-5718(1987)0866113-7
Keywords: Factorization, polynomial evaluation, elliptic curves, Lucas functions
Article copyright: © Copyright 1987 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia