## Speeding the Pollard and elliptic curve methods of factorization

HTML articles powered by AMS MathViewer

- by Peter L. Montgomery PDF
- Math. Comp.
**48**(1987), 243-264 Request permission

## 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

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The design and analysis of computer algorithms*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR**0413592**
Sara Baase, - Richard P. Brent,
*An improved Monte Carlo factorization algorithm*, BIT**20**(1980), no. 2, 176–184. MR**583032**, DOI 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 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 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 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) Congressus Numerantium, No. XVI, Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. MR**0404120** - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878** - D. H. Lehmer,
*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, DOI 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 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 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 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 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 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**, DOI 10.1007/978-1-4757-1089-2 - 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 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 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 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 10.1007/BF01389745 - H. C. Williams,
*A $p+1$ method of factoring*, Math. Comp.**39**(1982), no. 159, 225–234. MR**658227**, DOI 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.

## Additional Information

- © Copyright 1987 American Mathematical Society
- 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