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 $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*.

- 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**
Sara Baase, - Richard P. Brent,
*An improved Monte Carlo factorization algorithm*, BIT**20**(1980), no. 2, 176–184. MR**583032**, DOI https://doi.org/10.1007/BF01933190 - Richard P. Brent and John M. Pollard,
*Factorization of the eighth Fermat number*, Math. Comp.**36**(1981), no. 154, 627–630. MR**606520**, DOI https://doi.org/10.1090/S0025-5718-1981-0606520-5
R. P. Brent, "Some integer factorization algorithms using elliptic curves," presented to Australian Computer Science Conference, ACSC-9, 1986.
- John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr.,
*Factorizations of $b^{n}\pm 1$*, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR**715603**
John Brillhart, Peter L. Montgomery & Robert D. Silverman, "Tables of Fibonacci and Lucas factorizations." (In preparation.)
D. V. Chudnovsky & G. V. Chudnovsky, - Joseph L. Gerver,
*Factoring large numbers with a quadratic sieve*, Math. Comp.**41**(1983), no. 163, 287–294. MR**701639**, DOI https://doi.org/10.1090/S0025-5718-1983-0701639-4 - R. Gold and J. Sattler,
*Modifikationen des Pollard-Algorithmus*, Computing**30**(1983), no. 1, 77–89 (German, with English summary). MR**691952**, DOI https://doi.org/10.1007/BF02253297 - 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** - 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** - D. H. Lehmer,
*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, DOI https://doi.org/10.2307/1968235
H. W. Lenstra, Jr., "Elliptic curve factorization," announcement of February 14, 1985.
H. W. Lenstra, Jr., "Factoring integers with elliptic curves." (To appear.)
- Peter L. Montgomery,
*Modular multiplication without trial division*, Math. Comp.**44**(1985), no. 170, 519–521. MR**777282**, DOI https://doi.org/10.1090/S0025-5718-1985-0777282-X
Peter L. Montgomery, "Evaluation of ${V_n}(P,1)$ via Lucas chains," - Thorkil Naur,
*New integer factorizations*, Math. Comp.**41**(1983), no. 164, 687–695. MR**717713**, DOI https://doi.org/10.1090/S0025-5718-1983-0717713-2 - Michael A. Morrison and John Brillhart,
*A method of factoring and the factorization of $F_{7}$*, Math. Comp.**29**(1975), 183–205. MR**371800**, DOI https://doi.org/10.1090/S0025-5718-1975-0371800-5 - J. M. Pollard,
*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**354514**, DOI https://doi.org/10.1017/s0305004100049252 - J. M. Pollard,
*A Monte Carlo method for factorization*, Nordisk Tidskr. Informationsbehandling (BIT)**15**(1975), no. 3, 331–334. MR**392798**, DOI https://doi.org/10.1007/bf01933667
J. M. Pollard, private communication.
- Hans Riesel,
*Prime numbers and computer methods for factorization*, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR**897531** - 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**, DOI https://doi.org/10.1090/S0025-5718-1984-0744939-5 - J. T. Schwartz,
*Fast probabilistic algorithms for verification of polynomial identities*, J. Assoc. Comput. Mach.**27**(1980), no. 4, 701–717. MR**594695**, DOI https://doi.org/10.1145/322217.322225 - 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** - 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**
Robert D. Silverman, private communication.
- Robert D. Silverman,
*The multiple polynomial quadratic sieve*, Math. Comp.**48**(1987), no. 177, 329–339. MR**866119**, DOI https://doi.org/10.1090/S0025-5718-1987-0866119-8
Hiromi Suyama, "Informal preliminary report (8)," 25 Oct. 1985.
- John T. Tate,
*The arithmetic of elliptic curves*, Invent. Math.**23**(1974), 179–206. MR**419359**, DOI https://doi.org/10.1007/BF01389745 - H. C. Williams,
*A $p+1$ method of factoring*, Math. Comp.**39**(1982), no. 159, 225–234. MR**658227**, DOI https://doi.org/10.1090/S0025-5718-1982-0658227-7
H. C. Williams, private communication.
S. Winograd, "Evaluating polynomials using rational auxiliary functions,"

*Computer Algorithms: Introduction to Design and Analysis*, Addison-Wesley, Reading, Mass., 1983.

*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. James A. Davis & Diane B. Holdridge,

*Most Wanted Factorizations Using the Quadratic Sieve*, Sandia report SAND84-1658, August, 1984.

*Fibonacci Quart.*(Submitted.)

*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

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

Article copyright:
© Copyright 1987
American Mathematical Society