Finding suitable curves for the elliptic curve method of factorization

Atkin, A. O. L.; Morain, F.

doi:10.1090/S0025-5718-1993-1140645-1

Finding suitable curves for the elliptic curve method of factorization
HTML articles powered by AMS MathViewer

by A. O. L. Atkin and F. Morain PDF

Math. Comp. 60 (1993), 399-405 Request permission

Abstract:

Using the parametrizations of Kubert, we show how to produce infinite families of elliptic curves which have prescribed nontrivial torsion over Q and rank at least one. These curves can be used to speed up the ECM factorization algorithm of Lenstra. We also briefly discuss curves with complex multiplication in this context.

References

A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
J. S. Chahal, Topics in number theory, The University Series in Mathematics, Plenum Press, New York, 1988. MR 955797, DOI 10.1007/978-1-4899-0439-3
Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), no. 2, 193–237. MR 434947, DOI 10.1112/plms/s3-33.2.193
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
B. Mazur, Rational points on modular curves, Modular functions of one variable, V (Proc. Second Internat. Conf., Univ. Bonn, Bonn, 1976) Lecture Notes in Math., Vol. 601, Springer, Berlin, 1977, pp. 107–148. MR 0450283
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
Markus A. Reichert, Explicit determination of nontrivial torsion structures of elliptic curves over quadratic number fields, Math. Comp. 46 (1986), no. 174, 637–658. MR 829635, DOI 10.1090/S0025-5718-1986-0829635-X

Lehrbuch der Algebra

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