Remote Access Mathematics of Computation
Green Open Access

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
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 $ 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?)

  • [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 $ {b^n} \pm 1$, $ b = 2,3,5,6,7,10,11,12$ 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 $ {V_n}(P,1)$ 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 $ {F_7}$," 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 $ p + 1$ 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.

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

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

American Mathematical Society