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

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866113-7

MathSciNet review:
866113

Full-text PDF

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 and Monte Carlo methods. More recently, Williams published a 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 and ECM, looking for a match. Polynomial preconditioning lets us search a fixed table of size *n* with 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 *n* multiplications for arbitrary *P*.

**[1]**Alfred V. Aho, John E. Hopcroft & Jeffrey D. Ullman,*The Design and Analysis of Computer Algorithms*, Addison-Wesley, Reading, Mass., 1974. MR**0413592 (54:1706)****[2]**Sara Baase,*Computer Algorithms: Introduction to Design and Analysis*, Addison-Wesley, Reading, Mass., 1983.**[3]**Richard P. Brent, "An improved Monte Carlo factorization algorithm,"*BIT*, v. 20, 1980, pp. 176-184. MR**583032 (82a:10007)****[4]**Richard P. Brent & John M. Pollard, "Factorization of the eighth Fermat number,"*Math. Comp.*, v. 36, 1981, pp. 627-630. MR**606520 (83h:10014)****[5]**R. P. Brent, "Some integer factorization algorithms using elliptic curves," presented to Australian Computer Science Conference, ACSC-9, 1986.**[6]**John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman & S. S. Wagstaff, Jr.,*Factorizations of*,*Up to High Powers*, Contemp. Math., vol. 22, Amer. Math. Soc., Providence, R. I., 1983. MR**715603 (84k:10005)****[7]**John Brillhart, Peter L. Montgomery & Robert D. Silverman, "Tables of Fibonacci and Lucas factorizations." (In preparation.)**[8]**D. V. Chudnovsky & G. V. Chudnovsky,*Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests*, Research report RC 11262 (#50739), IBM Thomas J. Watson Research Center, Yorktown Heights, N. Y., 1985.**[9]**James A. Davis & Diane B. Holdridge,*Most Wanted Factorizations Using the Quadratic Sieve*, Sandia report SAND84-1658, August, 1984.**[10]**Joseph L. Gerver, "Factoring large numbers with a quadratic sieve,"*Math. Comp.*, v. 41, 1983, pp. 287-294. MR**701639 (85c:11122)****[11]**R. Gold & J. Sattler, "Modifikationen des Pollard-Algorithmus,"*Computing*, v. 30, 1983, pp. 77-89. MR**691952 (84h:10009)****[12]**Richard K. Guy, "How to factor a number,"*Congressus Numerantium XVI*, Proc. Fifth Manitoba Conf. on Numerical Math., Winnipeg, 1976, pp. 49-89. MR**0404120 (53:7924)****[13]**Donald E. Knuth,*The Art of Computer Programming, Vol. II, Seminumerical Algorithms*, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR**633878 (83i:68003)****[14]**D. H. Lehmer, "An extended theory of Lucas' functions,"*Ann. of Math.*(2), v. 31, 1930, pp. 419-448. MR**1502953****[15]**H. W. Lenstra, Jr., "Elliptic curve factorization," announcement of February 14, 1985.**[16]**H. W. Lenstra, Jr., "Factoring integers with elliptic curves." (To appear.)**[17]**Peter L. Montgomery, "Modular multiplication without trial division,"*Math. Comp.*, v. 44, 1985, pp. 519-521. MR**777282 (86e:11121)****[18]**Peter L. Montgomery, "Evaluation of via Lucas chains,"*Fibonacci Quart.*(Submitted.)**[19]**Thorkil Naur, "New integer factorizations,"*Math. Comp.*, v. 41, 1983, pp. 687-695. MR**717713 (85c:11123)****[20]**M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ,"*Math. Comp.*, v. 29, 1975, pp. 183-208. MR**0371800 (51:8017)****[21]**J. M. Pollard, "Theorems on factorization and primality testing,"*Proc. Cambridge Philos. Soc.*, v. 76, 1974, pp. 521-528. MR**0354514 (50:6992)****[22]**J. M. Pollard, "A Monte Carlo method for factorization,"*BIT*, v. 15, 1975, pp. 331-334. MR**0392798 (52:13611)****[23]**J. M. Pollard, private communication.**[24]**Hans Riesel,*Prime Numbers and Computer Methods for Factorization*, Birkhäuser Progress in Mathematics, vol. 57, Boston, 1985. MR**897531 (88k:11002)****[25]**C. P. Schnorr & H. W. Lenstra, Jr., "A Monte Carlo factoring algorithm with linear storage,"*Math. Comp.*, v. 43, 1984, pp. 289-311. MR**744939 (85d:11106)****[26]**J. T. Schwartz, "Fast probabilistic algorithms for verification of polynomial identities,"*J. Assoc. Comput. Mach.*, v. 27, 1980, pp. 701-717. MR**594695 (82m:68078)****[27]**R. Sedgewick & T. G. Szymanski,*The Complexity of Finding Periods*, Proc. Eleventh Annual ACM Symposium on Theory of Computing, ACM, New York, 1979, pp. 74-80. MR**564621 (81d:68133)****[28]**Daniel Shanks,*Class Number, a Theory of Factorization, and Genera*, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1971, pp. 415-440. MR**0316385 (47:4932)****[29]**Robert D. Silverman, private communication.**[30]**Robert D. Silverman, "The multiple polynomial quadratic sieve,"*Math. Comp.*, v. 48, 1987, pp. 329-339. MR**866119 (88c:11079)****[31]**Hiromi Suyama, "Informal preliminary report (8)," 25 Oct. 1985.**[32]**John T. Tate, "The arithmetic of elliptic curves,"*Invent. Math.*, v. 23, 1974, pp. 179-206. MR**0419359 (54:7380)****[33]**H. C. Williams, "A method of factoring,"*Math. Comp.*, v. 39, 1982, pp. 225-234. MR**658227 (83h:10016)****[34]**H. C. Williams, private communication.**[35]**S. Winograd, "Evaluating polynomials using rational auxiliary functions,"*IBM Technical Disclosure Bulletin*, v. 13, 1970, pp. 1133-1135.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866113-7

Keywords:
Factorization,
polynomial evaluation,
elliptic curves,
Lucas functions

Article copyright:
© Copyright 1987
American Mathematical Society