Constructing elliptic curves over finite fields with prescribed torsion

Sutherland, Andrew

doi:10.1090/S0025-5718-2011-02538-X

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

Constructing elliptic curves over finite fields with prescribed torsion

Author: Andrew V. Sutherland
Journal: Math. Comp. 81 (2012), 1131-1147
MSC (2010): Primary 11G05, 11G07; Secondary 11-04, 14H10
Posted: August 4, 2011
MathSciNet review: 2869053
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a method for constructing optimized equations for the modular curve using a local search algorithm on a suitably defined graph of birationally equivalent plane curves. We then apply these equations over a finite field $\mathbb{F}_q$ to efficiently generate elliptic curves with nontrivial -torsion by searching for affine points on $X_1(N)(\mathbb{F}_q)$ , and we give a fast method for generating curves with (or without) a point of order using .

1. A. O. L. Atkin and F. Morain, Finding suitable curves for the elliptic curve method of factorization, Math. Comp. 60 (1993), no. 201, 399–405. MR 1140645 (93k:11115), http://dx.doi.org/10.1090/S0025-5718-1993-1140645-1
2. Houria Baaziz, Equations for the modular curve 𝑋₁(𝑁) and models of elliptic curves with torsion points, Math. Comp. 79 (2010), no. 272, 2371–2386. MR 2684370 (2011i:11056), http://dx.doi.org/10.1090/S0025-5718-10-02332-X
3. Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 282–295. MR 2467854 (2009j:11200), http://dx.doi.org/10.1007/978-3-540-79456-1_19
4. Peter Caday and Andrew V. Sutherland, Optimized equations for via simulated annealing, 2010, poster presented at Algorithmic Number Theory Symposium-ANTS IX, http://ants9.org/slides/poster_caday.pdf.
5. Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren (eds.), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2162716 (2007f:14020)
6. Andreas Enge and Andrew V. Sutherland, Class invariants for the CRT method, Algorithmic Number Theory Symposium-ANTS IX (G. Hanrot, F. Morain, and E. Thomé, eds.), Lecture Notes in Computer Science, vol. 6197, Springer-Verlag, 2010, pp. 142-156.
7. Ernst-Ulrich Gekeler, The distribution of group structures on elliptic curves over finite prime fields, Doc. Math. 11 (2006), 119–142 (electronic). MR 2226271 (2007b:11143)
8. Benedict H. Gross, A tameness criterion for Galois representations associated to modular forms (mod 𝑝), Duke Math. J. 61 (1990), no. 2, 445–517. MR 1074305 (91i:11060), http://dx.doi.org/10.1215/S0012-7094-90-06119-8
9. Everett W. Howe, On the group orders of elliptic curves over finite fields, Compositio Math. 85 (1993), no. 2, 229–247. MR 1204781 (94a:11089)
10. Dale Husemoller, Elliptic curves, Graduate Texts in Mathematics, vol. 111, Springer-Verlag, New York, 1987. With an appendix by Ruth Lawrence. MR 868861 (88h:11039)
11. Daeyeol Jeon, Chang Heon Kim, and Euisung Park, On the torsion of elliptic curves over quartic number fields, J. London Math. Soc. (2) 74 (2006), no. 1, 1–12. MR 2254548 (2007m:11079), http://dx.doi.org/10.1112/S0024610706022940
12. Daeyeol Jeon, Chang Heon Kim, and Andreas Schweizer, On the torsion of elliptic curves over cubic number fields, Acta Arith. 113 (2004), no. 3, 291–301. MR 2069117 (2005f:11112), http://dx.doi.org/10.4064/aa113-3-6
13. Daeyeol Jeon and Chang Heon Kim, On the arithmetic of certain modular curves, Acta Arith. 130 (2007), no. 2, 181–193. MR 2357655 (2008m:11119), http://dx.doi.org/10.4064/aa130-2-7
14. Daeyeol Jeon, Chang Heon Kim, and Yoonjin Lee, Families of elliptic curves over quartic number fields with prescribed torsion subgroups, Mathematics of Computation 80 (2011), 2395-2410.
15. Daeyeol Jeon, Chang Heon Kim, and Yoonjin Lee, Families of elliptic curves over cubic number fields with prescribed torsion subgroups, Math. Comp. 80 (2011), no. 273, 579–591. MR 2728995 (2011m:11113), http://dx.doi.org/10.1090/S0025-5718-10-02369-0
16. S. Kamienny and B. Mazur, Rational torsion of prime order in elliptic curves over number fields, Astérisque 228 (1995), 3, 81–100. With an appendix by A. Granville; Columbia University Number Theory Seminar (New York, 1992). MR 1330929 (96c:11058)
17. Anthony W. Knapp, Elliptic curves, Mathematical Notes, vol. 40, Princeton University Press, Princeton, NJ, 1992. MR 1193029 (93j:11032)
18. Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), no. 2, 193–237. MR 0434947 (55 #7910)
19. 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 (56 #8579)
20. Loïc Merel, Bornes pour la torsion des courbes elliptiques sur les corps de nombres, Invent. Math. 124 (1996), no. 1-3, 437–449 (French). MR 1369424 (96i:11057), http://dx.doi.org/10.1007/s002220050059
21. J. Miret, R. Moreno, A. Rio, and M. Valls, Determining the 2-Sylow subgroup of an elliptic curve over a finite field, Math. Comp. 74 (2005), no. 249, 411–427 (electronic). MR 2085900 (2005d:11090), http://dx.doi.org/10.1090/S0025-5718-04-01640-0
22. Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113 (88e:11130), http://dx.doi.org/10.1090/S0025-5718-1987-0866113-7
23. Pierre Parent, Bornes effectives pour la torsion des courbes elliptiques sur les corps de nombres, J. Reine Angew. Math. 506 (1999), 85–116 (French, with French summary). MR 1665681 (99k:11080), http://dx.doi.org/10.1515/crll.1999.009
24. 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 (87f:11039), http://dx.doi.org/10.1090/S0025-5718-1986-0829635-X
25. Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210 (87g:11070)
26. Neil J. A. Sloane, The on-line encyclopedia of integer sequences, 2010, published electronically at http://oeis.org.
27. Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501–538. MR 2728992 (2011k:11177), http://dx.doi.org/10.1090/S0025-5718-2010-02373-7
28. Richard G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106. MR 0144891 (26 #2432)
29. Yifan Yang, Defining equations of modular curves, Adv. Math. 204 (2006), no. 2, 481–508. MR 2249621 (2007e:11068), http://dx.doi.org/10.1016/j.aim.2005.05.019
30. Andrew Chi Chih Yao, On the evaluation of powers, SIAM J. Comput. 5 (1976), no. 1, 100–103. MR 0395331 (52 #16128)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|