Speeding the Pollard and elliptic curve methods of factorization

Montgomery, Peter L.

doi:10.1090/S0025-5718-1987-0866113-7

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

Computer Algorithms: Introduction to Design and Analysis

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

Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests

Most Wanted Factorizations Using the Quadratic Sieve

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

Fibonacci Quart.

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
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, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329–339. MR 866119, DOI 10.1090/S0025-5718-1987-0866119-8
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

IBM Technical Disclosure Bulletin