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.

**[1]**A. O. L. Atkin and F. Morain,*Elliptic curves and primality proving*, Math. Comp.**61**(1993), no. 203, 29–68. MR**1199989**, 10.1090/S0025-5718-1993-1199989-X**[2]**John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr.,*Factorizations of 𝑏ⁿ±1*, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR**996414****[3]**J. S. Chahal,*Topics in number theory*, The University Series in Mathematics, Plenum Press, New York, 1988. MR**955797****[4]**Daniel Sion Kubert,*Universal bounds on the torsion of elliptic curves*, Proc. London Math. Soc. (3)**33**(1976), no. 2, 193–237. MR**0434947****[5]**H. W. Lenstra Jr.,*Factoring integers with elliptic curves*, Ann. of Math. (2)**126**(1987), no. 3, 649–673. MR**916721**, 10.2307/1971363**[6]**B. Mazur,*Rational points on modular curves*, Modular functions of one variable, V (Proc. Second Internat. Conf., Univ. Bonn, Bonn, 1976) Springer, Berlin, 1977, pp. 107–148. Lecture Notes in Math., Vol. 601. MR**0450283****[7]**Peter L. Montgomery,*Speeding the Pollard and elliptic curve methods of factorization*, Math. Comp.**48**(1987), no. 177, 243–264. MR**866113**, 10.1090/S0025-5718-1987-0866113-7**[8]**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**, 10.1090/S0025-5718-1986-0829635-X**[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 𝑝+1 method of factoring*, Math. Comp.**39**(1982), no. 159, 225–234. MR**658227**, 10.1090/S0025-5718-1982-0658227-7

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

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

Additional Information

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

Article copyright:
© Copyright 1993
American Mathematical Society