Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Finding suitable curves for the elliptic curve method of factorization

Authors: A. O. L. Atkin and F. Morain
Journal: Math. Comp. 60 (1993), 399-405
MSC: Primary 11Y05; Secondary 11G20
MathSciNet review: 1140645
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Research Report 1256, INRIA, Juin 1990; Math. Comp. (to appear). MR 1199989 (93m:11136)
  • [2] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $ {b^n} \pm 1,b = 2,3,5,6,7,10,11,12$ up to high powers, 2nd ed., Contemp. Math., vol. 22, Amer. Math. Soc., Providence, RI, 1988. MR 996414 (90d:11009)
  • [3] J. S. Chahal, Topics in number theory, Plenum Press, 1988. MR 955797 (89m:11001)
  • [4] D. S. Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), 193-237. MR 0434947 (55:7910)
  • [5] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 916721 (89g:11125)
  • [6] B. Mazur, Rational points on modular curves, Modular Forms of One Variable V (Proc. Internat. Conf., University of Bonn), Lecture Notes in Math., vol. 601, Springer-Verlag, 1977, pp. 107-148. MR 0450283 (56:8579)
  • [7] P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243-264. MR 866113 (88e:11130)
  • [8] M. A. Reichert, Explicit determination of nontrivial torsion structures of elliptic curves over quadratic number fields, Math. Comp. 46 (1986), 637-658. MR 829635 (87f:11039)
  • [9] H. Suyama, Informal preliminary report (8), Oct. 25, 1985.
  • [10] H. Weber, Lehrbuch der Algebra, vols. I, II, III, Chelsea, New York, 1902.
  • [11] H. C. Williams, A $ p + 1$ method of factoring, Math. Comp. 39 (1982), 225-234. MR 658227 (83h:10016)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11G20

Retrieve articles in all journals with MSC: 11Y05, 11G20

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society