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