Constructing elliptic curves over finite fields with prescribed torsion
HTML articles powered by AMS MathViewer
- by Andrew V. Sutherland;
- Math. Comp. 81 (2012), 1131-1147
- DOI: https://doi.org/10.1090/S0025-5718-2011-02538-X
- Published electronically: August 4, 2011
- PDF | 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-New York, 1977, pp. 107–148. MR 450283
- 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
Bibliographic Information
- Andrew V. Sutherland
- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- MR Author ID: 852273
- ORCID: 0000-0001-7739-2792
- Email: drew@math.mit.edu
- Received by editor(s): September 21, 2010
- Received by editor(s) in revised form: February 20, 2011
- Published electronically: August 4, 2011
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 81 (2012), 1131-1147
- MSC (2010): Primary 11G05, 11G07; Secondary 11-04, 14H10
- DOI: https://doi.org/10.1090/S0025-5718-2011-02538-X
- MathSciNet review: 2869053