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

DOI:
https://doi.org/10.1090/S0025-5718-1993-1140645-1

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.

**[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**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**method of factoring*, Math. Comp.**39**(1982), 225-234. MR**658227 (83h:10016)**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1140645-1

Article copyright:
© Copyright 1993
American Mathematical Society