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 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 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, and Jeffrey D. Ullman,*The design and analysis of computer algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR**0413592****[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**20**(1980), no. 2, 176–184. MR**583032**, https://doi.org/10.1007/BF01933190**[4]**Richard P. Brent and John M. Pollard,*Factorization of the eighth Fermat number*, Math. Comp.**36**(1981), no. 154, 627–630. MR**606520**, https://doi.org/10.1090/S0025-5718-1981-0606520-5**[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, and S. S. Wagstaff Jr.,*Factorizations of 𝑏ⁿ±1*, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR**715603****[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.**41**(1983), no. 163, 287–294. MR**701639**, https://doi.org/10.1090/S0025-5718-1983-0701639-4**[11]**R. Gold and J. Sattler,*Modifikationen des Pollard-Algorithmus*, Computing**30**(1983), no. 1, 77–89 (German, with English summary). MR**691952**, https://doi.org/10.1007/BF02253297**[12]**Richard K. Guy,*How to factor a number*, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. Congressus Numerantium, No. XVI. MR**0404120****[13]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[14]**D. H. Lehmer,*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, https://doi.org/10.2307/1968235**[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.**44**(1985), no. 170, 519–521. MR**777282**, https://doi.org/10.1090/S0025-5718-1985-0777282-X**[18]**Peter L. Montgomery, "Evaluation of via Lucas chains,"*Fibonacci Quart.*(Submitted.)**[19]**Thorkil Naur,*New integer factorizations*, Math. Comp.**41**(1983), no. 164, 687–695. MR**717713**, https://doi.org/10.1090/S0025-5718-1983-0717713-2**[20]**Michael A. Morrison and John Brillhart,*A method of factoring and the factorization of 𝐹₇*, Math. Comp.**29**(1975), 183–205. MR**371800**, https://doi.org/10.1090/S0025-5718-1975-0371800-5**[21]**J. M. Pollard,*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**354514**, https://doi.org/10.1017/s0305004100049252**[22]**J. M. Pollard,*A Monte Carlo method for factorization*, Nordisk Tidskr. Informationsbehandling (BIT)**15**(1975), no. 3, 331–334. MR**392798**, https://doi.org/10.1007/bf01933667**[23]**J. M. Pollard, private communication.**[24]**Hans Riesel,*Prime numbers and computer methods for factorization*, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR**897531****[25]**C.-P. Schnorr and H. W. Lenstra Jr.,*A Monte Carlo factoring algorithm with linear storage*, Math. Comp.**43**(1984), no. 167, 289–311. MR**744939**, https://doi.org/10.1090/S0025-5718-1984-0744939-5**[26]**J. T. Schwartz,*Fast probabilistic algorithms for verification of polynomial identities*, J. Assoc. Comput. Mach.**27**(1980), no. 4, 701–717. MR**594695**, https://doi.org/10.1145/322217.322225**[27]**Robert Sedgewick and Thomas G. Szymanski,*The complexity of finding periods*, Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979) ACM, New York, 1979, pp. 74–80. MR**564621****[28]**Daniel Shanks,*Class number, a theory of factorization, and genera*, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR**0316385****[29]**Robert D. Silverman, private communication.**[30]**Robert D. Silverman,*The multiple polynomial quadratic sieve*, Math. Comp.**48**(1987), no. 177, 329–339. MR**866119**, https://doi.org/10.1090/S0025-5718-1987-0866119-8**[31]**Hiromi Suyama, "Informal preliminary report (8)," 25 Oct. 1985.**[32]**John T. Tate,*The arithmetic of elliptic curves*, Invent. Math.**23**(1974), 179–206. MR**419359**, https://doi.org/10.1007/BF01389745**[33]**H. C. Williams,*A 𝑝+1 method of factoring*, Math. Comp.**39**(1982), no. 159, 225–234. MR**658227**, https://doi.org/10.1090/S0025-5718-1982-0658227-7**[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