Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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
DOI: https://doi.org/10.1090/S0025-5718-2011-02538-X
Published electronically: August 4, 2011
MathSciNet review: 2869053
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. A.O.L. Atkin and François Morain, Finding suitable curves for the elliptic curve method of factorization, Mathematics of Computation 60 (1993), 399-405. MR 1140645 (93k:11115)
  • 2. Houria Baaziz, Equations for the modular curve $ X_1(N)$ and models of elliptic curves with torsion points, Mathematics of Computation 79 (2010), no. 272, 2371-2386. MR 2684370
  • 3. Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic Number Theory Symposium-ANTS VIII (A. J. van der Poorten and A. Stein, eds.), Lecture Notes in Computer Science, vol. 5011, Springer, 2008, pp. 282-295. MR 2467854 (2009j:11200)
  • 4. 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.
  • 5. Henri Cohen and Gerhard Frey et al., Handbook of elliptic and hyperelliptic curve cryptography, Chapman and Hall, 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, Documenta Mathematica 11 (2006), 119-142. MR 2226271 (2007b:11143)
  • 8. Benedict H. Gross, A tameness criterion for Galois representations associated to modular forms (mod $ p$)., Duke Mathematical Journal 61 (1990), no. 2, 445-517. MR 1074305 (91i:11060)
  • 9. Everett W. Howe, On the group orders of elliptic curves over finite fields, Compositio Mathematica 85 (1993), 229-247. MR 1204781 (94a:11089)
  • 10. Dale Husemöller, Elliptic curves, Springer-Verlag, 1987. MR 868861 (88h:11039)
  • 11. Daeyeol Jeon, Chang Heon Kim, and Euisung Park, On the torsion of elliptic curves over quartic number fields, Journal of the London Mathematical Society 74 (2006), 1-12. MR 2254548 (2007m:11079)
  • 12. Daeyeol Jeon, Chang Heon Kim, and Andreas Schweizer, On the torsion of elliptic curves over cubic number fields, Acta Arithmetica 113 (2004), 291-301. MR 2069117 (2005f:11112)
  • 13. Daeyeol Jeon and Chang Heon Kim, On the arithmetic of certain modular curves, Acta Arithmetica 130 (2007), no. 2, 181-194. MR 2357655 (2008m:11119)
  • 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. -, Families of elliptic curves over cubic number fields with prescribed torsion subgroups, Mathematics of Computation 80 (2011), 579-591. MR 2728995
  • 16. Sheldon Kamienny and Barry Mazur, Rational torsion of prime order in elliptic curves over number fields, Astérisque (1995), no. 228, 81-100. MR 1330929 (96c:11058)
  • 17. Anthony W. Knapp, Elliptic curves, Princeton University Press, 1992. MR 1193029 (93j:11032)
  • 18. Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proceedings of the London Mathematical Society 33 (1976), 193-237. MR 0434947 (55:7910)
  • 19. Barry Mazur, Rational points on modular curves, Modular Forms of One Variable V, Lecture Notes in Mathematics, vol. 601, Springer-Verlag, 1977, pp. 107-148. MR 0450283 (56:8579)
  • 20. Loïc Merel, Bornes pour la torsion des courbes elliptiques sur les corps de nombres, Inventiones Mathematicae 124 (1996), 437-449. MR 1369424 (96i:11057)
  • 21. J. Miret, R. Moreno, A. Rio, and M. Valls, Determining the $ 2$-sylow subgroup of an elliptic curve over a finite field, Mathematics of Computation 74 (2005), no. 249, 411-427. MR 2085900 (2005d:11090)
  • 22. Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Mathematics of Computation 48 (1987), no. 177, 243-264. MR 866113 (88e:11130)
  • 23. Pierre Parent, Bornes effectives pour la torsion des courbes elliptiques sur les corps de nombres, Journal für die reine und angewandte Mathematik 506 (1999), 85-116. MR 1665681 (99k:11080)
  • 24. Markus A. Reichert, Explicit determination of nontrivial torsion structures of elliptic curves over quadratic number fields, Mathematics of Computation 46 (1986), no. 174, 637-658. MR 829635 (87f:11039)
  • 25. Joseph H. Silverman, The arithmetic of elliptic curves, Springer, 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, Mathematics of Computation 80 (2011), 501-538. MR 2728992
  • 28. Richard G. Swan, Factorization of polynomials over finite fields, Pacific Journal of Mathematics 12 (1962), no. 3, 1099-1106. MR 0144891 (26:2432)
  • 29. Yifan Yang, Defining equations for modular curves, Advances in Mathematics 204 (2006), no. 2, 481-508. MR 2249621 (2007e:11068)
  • 30. Andrew C. Yao, On the evaluation of powers, SIAM Journal of Computing 5 (1976), 100-103. MR 0395331 (52:16128)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11G05, 11G07, 11-04, 14H10

Retrieve articles in all journals with MSC (2010): 11G05, 11G07, 11-04, 14H10


Additional Information

Andrew V. Sutherland
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: drew@math.mit.edu

DOI: https://doi.org/10.1090/S0025-5718-2011-02538-X
Received by editor(s): September 21, 2010
Received by editor(s) in revised form: February 20, 2011
Published electronically: August 4, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society