Speeding the Pollard and elliptic curve methods of factorization
Author:
Peter L. Montgomery
Journal:
Math. Comp. 48 (1987), 243264
MSC:
Primary 11Y05; Secondary 11A51, 68Q40
MathSciNet review:
866113
Fulltext 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 xcoordinate 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,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley Series in Computer Science and Information
Processing. MR
0413592 (54 #1706)
 [2]
Sara Baase, Computer Algorithms: Introduction to Design and Analysis, AddisonWesley, Reading, Mass., 1983.
 [3]
Richard
P. Brent, An improved Monte Carlo factorization algorithm, BIT
20 (1980), no. 2, 176–184. MR 583032
(82a:10007), http://dx.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
(83h:10014), http://dx.doi.org/10.1090/S00255718198106065205
 [5]
R. P. Brent, "Some integer factorization algorithms using elliptic curves," presented to Australian Computer Science Conference, ACSC9, 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
(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 SAND841658, August, 1984.
 [10]
Joseph
L. Gerver, Factoring large numbers with a
quadratic sieve, Math. Comp.
41 (1983), no. 163, 287–294. MR 701639
(85c:11122), http://dx.doi.org/10.1090/S00255718198307016394
 [11]
R.
Gold and J.
Sattler, Modifikationen des PollardAlgorithmus, Computing
30 (1983), no. 1, 77–89 (German, with English
summary). MR
691952 (84h:10009), http://dx.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
(53 #7924)
 [13]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [14]
D.
H. Lehmer, An extended theory of Lucas’ functions, Ann.
of Math. (2) 31 (1930), no. 3, 419–448. MR
1502953, http://dx.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
(86e:11121), http://dx.doi.org/10.1090/S0025571819850777282X
 [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
(85c:11123), http://dx.doi.org/10.1090/S00255718198307177132
 [20]
Michael
A. Morrison and John
Brillhart, A method of factoring and the
factorization of 𝐹₇, Math.
Comp. 29 (1975),
183–205. Collection of articles dedicated to Derrick Henry Lehmer on
the occasion of his seventieth birthday. MR 0371800
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [21]
J.
M. Pollard, Theorems on factorization and primality testing,
Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
(50 #6992)
 [22]
J.
M. Pollard, A Monte Carlo method for factorization, Nordisk
Tidskr. Informationsbehandling (BIT) 15 (1975),
no. 3, 331–334. MR 0392798
(52 #13611)
 [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
(88k:11002)
 [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
(85d:11106), http://dx.doi.org/10.1090/S00255718198407449395
 [26]
J.
T. Schwartz, Fast probabilistic algorithms for verification of
polynomial identities, J. Assoc. Comput. Mach. 27
(1980), no. 4, 701–717. MR 594695
(82m:68078), http://dx.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
(81d:68133)
 [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
(47 #4932)
 [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
(88c:11079), http://dx.doi.org/10.1090/S00255718198708661198
 [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 0419359
(54 #7380)
 [33]
H.
C. Williams, A 𝑝+1 method of
factoring, Math. Comp. 39
(1982), no. 159, 225–234. MR 658227
(83h:10016), http://dx.doi.org/10.1090/S00255718198206582277
 [34]
H. C. Williams, private communication.
 [35]
S. Winograd, "Evaluating polynomials using rational auxiliary functions," IBM Technical Disclosure Bulletin, v. 13, 1970, pp. 11331135.
 [1]
 Alfred V. Aho, John E. Hopcroft & Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, AddisonWesley, Reading, Mass., 1974. MR 0413592 (54:1706)
 [2]
 Sara Baase, Computer Algorithms: Introduction to Design and Analysis, AddisonWesley, Reading, Mass., 1983.
 [3]
 Richard P. Brent, "An improved Monte Carlo factorization algorithm," BIT, v. 20, 1980, pp. 176184. MR 583032 (82a:10007)
 [4]
 Richard P. Brent & John M. Pollard, "Factorization of the eighth Fermat number," Math. Comp., v. 36, 1981, pp. 627630. MR 606520 (83h:10014)
 [5]
 R. P. Brent, "Some integer factorization algorithms using elliptic curves," presented to Australian Computer Science Conference, ACSC9, 1986.
 [6]
 John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman & S. S. Wagstaff, Jr., Factorizations of , 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 SAND841658, August, 1984.
 [10]
 Joseph L. Gerver, "Factoring large numbers with a quadratic sieve," Math. Comp., v. 41, 1983, pp. 287294. MR 701639 (85c:11122)
 [11]
 R. Gold & J. Sattler, "Modifikationen des PollardAlgorithmus," Computing, v. 30, 1983, pp. 7789. 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. 4989. MR 0404120 (53:7924)
 [13]
 Donald E. Knuth, The Art of Computer Programming, Vol. II, Seminumerical Algorithms, 2nd ed., AddisonWesley, 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. 419448. 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. 519521. MR 777282 (86e:11121)
 [18]
 Peter L. Montgomery, "Evaluation of via Lucas chains," Fibonacci Quart. (Submitted.)
 [19]
 Thorkil Naur, "New integer factorizations," Math. Comp., v. 41, 1983, pp. 687695. MR 717713 (85c:11123)
 [20]
 M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ," Math. Comp., v. 29, 1975, pp. 183208. MR 0371800 (51:8017)
 [21]
 J. M. Pollard, "Theorems on factorization and primality testing," Proc. Cambridge Philos. Soc., v. 76, 1974, pp. 521528. MR 0354514 (50:6992)
 [22]
 J. M. Pollard, "A Monte Carlo method for factorization," BIT, v. 15, 1975, pp. 331334. 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. 289311. MR 744939 (85d:11106)
 [26]
 J. T. Schwartz, "Fast probabilistic algorithms for verification of polynomial identities," J. Assoc. Comput. Mach., v. 27, 1980, pp. 701717. 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. 7480. 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. 415440. 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. 329339. 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. 179206. MR 0419359 (54:7380)
 [33]
 H. C. Williams, "A method of factoring," Math. Comp., v. 39, 1982, pp. 225234. 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. 11331135.
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:
http://dx.doi.org/10.1090/S00255718198708661137
PII:
S 00255718(1987)08661137
Keywords:
Factorization,
polynomial evaluation,
elliptic curves,
Lucas functions
Article copyright:
© Copyright 1987
American Mathematical Society
