Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 

 

Modular equations for hyperelliptic curves


Authors: P. Gaudry and É. Schost
Journal: Math. Comp. 74 (2005), 429-454
MSC (2000): Primary 11Y40; Secondary 11G20, 11Y16
Published electronically: May 25, 2004
MathSciNet review: 2085901
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define modular equations describing the $\ell$-torsion subgroups of the Jacobian of a hyperelliptic curve. Over a finite base field, we prove factorization properties that extend the well-known results used in Atkin's improvement of Schoof's genus 1 point counting algorithm.


References [Enhancements On Off] (What's this?)

  • 1. Magma, http://www.maths.usyd.edu.au:8000/u/magma/.
  • 2. Medicis, http://www.medicis.polytechnique.fr/.
  • 3. Tera, http://tera.medicis.polytechnique.fr/.
  • 4. L. Adleman and M.-D. Huang, Counting points on curves and abelian varieties over finite fields, J. Symbolic Comput. 32 (2001), 171-189. MR 2002j:14027
  • 5. A. O. L. Atkin, The number of points on an elliptic curve modulo a prime, Series of e-mails to the NMBRTHRY mailing list, 1992.
  • 6. I. Blake, G. Seroussi, and N. Smart, Elliptic curves in cryptography, London Math. Soc. Lecture Note Ser., vol. 265, Cambridge University Press, 1999. MR 2001i:94048
  • 7. J. Boxall and D. Grant, Examples of torsion points on genus two curves, Trans. Amer. Math. Soc. 352 (2000), 4533-4555. MR 2001b:11057
  • 8. B. Buchberger, Gröbner bases: An algorithmic method in polynomial ideal theory, Chapter 6, in N. K. Bose et al., Multidimensional Systems Theory, Reidel, Dordrecht, 1985, pp. 374-383. MR 87m:93017
  • 9. D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), 95-101.MR 88f:11118
  • 10. -, On the analogue of the division polynomials for hyperelliptic curves, J. Reine Angew. Math. 447 (1994), 91-145.MR 94m:11071
  • 11. L. S. Charlap, R. Coley, and D. P. Robbins, Enumeration of rational points on elliptic curves over finite fields, Draft, 1991.
  • 12. N. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational Perspectives on Number Theory (D.A. Buell and J.T. Teitelbaum, eds.), AMS/International Press, 1998, Proceedings of a Conference in Honor of A.O.L. Atkin, pp. 21-76. MR 99a:11078
  • 13. P. Gaudry and R. Harley, Counting points on hyperelliptic curves over finite fields, ANTS-IV (W. Bosma, ed.), Lecture Notes in Comput. Sci., vol. 1838, Springer-Verlag, 2000, pp. 313-332.MR 2002f:11072
  • 14. M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo, Straight-line programs in geometric elimination theory, J. of Pure and App. Algebra 124 (1998), 101-146.MR 99d:68128
  • 15. M. Giusti, G. Lecerf, and B. Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), 154-211. MR 2002b:68123
  • 16. J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein, Deformation techniques for efficient polynomial equation solving, J. Complexity 16 (2000), 70-109.MR 2001c:65067
  • 17. M. Hindry and J. Silverman, Diophantine geometry. an introduction, Graduate Texts in Mathematics, vol. 201, Springer-Verlag, 2000. MR 2001e:11058
  • 18. M.-D. Huang and D. Ierardi, Counting points on curves over finite fields, J. Symbolic Comput. 25 (1998), 1-21.MR 98i:11040
  • 19. C. Dicrescenzo J. Della Dora and D. Duval, About a new method for computing in algebraic number fields, Proceedings Eurocal '85 Vol. 2, Lecture Notes in Comput. Sci., vol. 204, 1985, pp. 289-290.
  • 20. E. Kaltofen and V. Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp., 67 (1998), 1179-1197. MR 99m:68097
  • 21. W. Kampkötter, Explizite Gleichungen für Jacobische Varietäten hyperelliptischer Kurven, Ph.D. thesis, Universität Gesamthochschule Essen, August 1991.
  • 22. J. S. Milne, Abelian varieties, Arithmetic Geometry (G. Cornell and J. H. Silverman, eds.), Springer-Verlag, 1986, pp. 103-150. MR 89b:14029
  • 23. -, Jacobian varieties, Arithmetic Geometry (G. Cornell and J. H. Silverman, eds.), Springer-Verlag, 1986, pp. 167-212.MR 89b:14029
  • 24. F. Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), 255-282.MR 97i:11069
  • 25. D. Mumford, Tata lectures on theta I, Progr. Math., vol. 28, Birkhäuser, 1983.MR 85h:14026
  • 26. J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), 745-763.MR 91a:11071
  • 27. R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), 483-494.MR 86e:11122
  • 28. -, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), 219-254.MR 97i:11070
  • 29. É. Schost, Complexity results for triangular sets, J. Symbolic Comput. 36 (2003), 555-594.
  • 30. J. H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, 1986.MR 87g:11070
  • 31. J. von zur Gathen and J. Gerhard, Modern computer algebra, Cambridge University Press, 1999.MR 2000j:68205
  • 32. D. Y. Y. Yun, On square-free decompositions algorithms, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, ACM Press, 1976, pp. 26-35.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y40, 11G20, 11Y16

Retrieve articles in all journals with MSC (2000): 11Y40, 11G20, 11Y16


Additional Information

P. Gaudry
Affiliation: Laboratoire LIX, École polytechnique, 91128 Palaiseau, France
Email: gaudry@lix.polytechnique.fr

É. Schost
Affiliation: Laboratoire STIX, École polytechnique, 91128 Palaiseau, France
Email: schost@stix.polytechnique.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-04-01682-5
Keywords: Modular equations, hyperelliptic curves, Schoof-Elkies-Atkin algorithm
Received by editor(s): July 15, 2002
Received by editor(s) in revised form: August 16, 2003
Published electronically: May 25, 2004
Article copyright: © Copyright 2004 Copyright held by the authors