Constructing elliptic curves over finite fields with prescribed torsion

Sutherland, Andrew

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

Constructing elliptic curves over finite fields with prescribed torsion
HTML articles powered by AMS MathViewer

by Andrew V. Sutherland PDF

Math. Comp. 81 (2012), 1131-1147 Request permission

Abstract:

We present a method for constructing optimized equations for the modular curve $X_1(N)$ 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 $N$-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 $4N$ using $X_1(2N)$.

References

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, DOI 10.1090/S0025-5718-1993-1140645-1
Houria Baaziz, Equations for the modular curve $X_1(N)$ and models of elliptic curves with torsion points, Math. Comp. 79 (2010), no. 272, 2371–2386. MR 2684370, DOI 10.1090/S0025-5718-10-02332-X
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, DOI 10.1007/978-3-540-79456-1_{1}9
Peter Caday and Andrew V. Sutherland, Optimized equations for $X_1(N)$ via simulated annealing, 2010, poster presented at Algorithmic Number Theory Symposium–ANTS IX, http://ants9.org/slides/poster_caday.pdf.
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
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.
Ernst-Ulrich Gekeler, The distribution of group structures on elliptic curves over finite prime fields, Doc. Math. 11 (2006), 119–142. MR 2226271
Benedict H. Gross, A tameness criterion for Galois representations associated to modular forms (mod $p$), Duke Math. J. 61 (1990), no. 2, 445–517. MR 1074305, DOI 10.1215/S0012-7094-90-06119-8
Everett W. Howe, On the group orders of elliptic curves over finite fields, Compositio Math. 85 (1993), no. 2, 229–247. MR 1204781
Dale Husemoller, Elliptic curves, Graduate Texts in Mathematics, vol. 111, Springer-Verlag, New York, 1987. With an appendix by Ruth Lawrence. MR 868861, DOI 10.1007/978-1-4757-5119-2
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, DOI 10.1112/S0024610706022940
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, DOI 10.4064/aa113-3-6
Daeyeol Jeon and Chang Heon Kim, On the arithmetic of certain modular curves, Acta Arith. 130 (2007), no. 2, 181–193. MR 2357655, DOI 10.4064/aa130-2-7
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.
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, DOI 10.1090/S0025-5718-10-02369-0
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
Anthony W. Knapp, Elliptic curves, Mathematical Notes, vol. 40, Princeton University Press, Princeton, NJ, 1992. MR 1193029
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
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
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, DOI 10.1007/s002220050059
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. MR 2085900, DOI 10.1090/S0025-5718-04-01640-0
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
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, DOI 10.1515/crll.1999.009
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
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Neil J. A. Sloane, The on-line encyclopedia of integer sequences, 2010, published electronically at http://oeis.org.
Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501–538. MR 2728992, DOI 10.1090/S0025-5718-2010-02373-7
Richard G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106. MR 144891
Yifan Yang, Defining equations of modular curves, Adv. Math. 204 (2006), no. 2, 481–508. MR 2249621, DOI 10.1016/j.aim.2005.05.019
Andrew Chi Chih Yao, On the evaluation of powers, SIAM J. Comput. 5 (1976), no. 1, 100–103. MR 395331, DOI 10.1137/0205008