Modular equations for hyperelliptic curves

Gaudry, P.; Schost, É.

doi:10.1090/S0025-5718-04-01682-5

Modular equations for hyperelliptic curves
HTML articles powered by AMS MathViewer

by P. Gaudry and É. Schost PDF

Math. Comp. 74 (2005), 429-454

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

Magma, http://www.maths.usyd.edu.au:8000/u/magma/.
Medicis, http://www.medicis.polytechnique.fr/.
Tera, http://tera.medicis.polytechnique.fr/.
Leonard M. Adleman and Ming-Deh Huang, Counting points on curves and abelian varieties over finite fields, J. Symbolic Comput. 32 (2001), no. 3, 171–189. MR 1851164, DOI 10.1006/jsco.2001.0470
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.
I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549
John Boxall and David Grant, Examples of torsion points on genus two curves, Trans. Amer. Math. Soc. 352 (2000), no. 10, 4533–4555. MR 1621721, DOI 10.1090/S0002-9947-00-02368-0
N. K. Bose, J. P. Guiver, E. W. Kamen, H. M. Valenzuela, and B. Buchberger, Multidimensional systems theory, Mathematics and its Applications, vol. 16, D. Reidel Publishing Co., Dordrecht, 1985. Progress, directions and open problems in multidimensional systems. MR 804981, DOI 10.1007/978-94-009-5225-6
David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95–101. MR 866101, DOI 10.1090/S0025-5718-1987-0866101-0
David G. Cantor, On the analogue of the division polynomials for hyperelliptic curves, J. Reine Angew. Math. 447 (1994), 91–145. MR 1263171, DOI 10.1515/crll.1994.447.91
L. S. Charlap, R. Coley, and D. P. Robbins, Enumeration of rational points on elliptic curves over finite fields, Draft, 1991.
Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21–76. MR 1486831, DOI 10.1090/amsip/007/03
Pierrick Gaudry and Robert Harley, Counting points on hyperelliptic curves over finite fields, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 313–332. MR 1850614, DOI 10.1007/10722028_{1}8
M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo, Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra 124 (1998), no. 1-3, 101–146. MR 1600277, DOI 10.1016/S0022-4049(96)00099-0
Marc Giusti, Grégoire Lecerf, and Bruno Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154–211. MR 1817612, DOI 10.1006/jcom.2000.0571
Joos Heintz, Teresa Krick, Susana Puddu, Juan Sabia, and Ariel Waissbein, Deformation techniques for efficient polynomial equation solving, J. Complexity 16 (2000), no. 1, 70–109. Real computation and complexity (Schloss Dagstuhl, 1998). MR 1762400, DOI 10.1006/jcom.1999.0529
Marc Hindry and Joseph H. Silverman, Diophantine geometry, Graduate Texts in Mathematics, vol. 201, Springer-Verlag, New York, 2000. An introduction. MR 1745599, DOI 10.1007/978-1-4612-1210-2
Ming-Deh Huang and Doug Ierardi, Counting points on curves over finite fields, J. Symbolic Comput. 25 (1998), no. 1, 1–21. MR 1600606, DOI 10.1006/jsco.1997.0164
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.
Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
W. Kampkötter, Explizite Gleichungen für Jacobische Varietäten hyperelliptischer Kurven, Ph.D. thesis, Universität Gesamthochschule Essen, August 1991.
Gary Cornell and Joseph H. Silverman (eds.), Arithmetic geometry, Springer-Verlag, New York, 1986. Papers from the conference held at the University of Connecticut, Storrs, Connecticut, July 30–August 10, 1984. MR 861969, DOI 10.1007/978-1-4613-8655-1
Gary Cornell and Joseph H. Silverman (eds.), Arithmetic geometry, Springer-Verlag, New York, 1986. Papers from the conference held at the University of Connecticut, Storrs, Connecticut, July 30–August 10, 1984. MR 861969, DOI 10.1007/978-1-4613-8655-1
François Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 255–282 (French, with English and French summaries). Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413579
David Mumford, Tata lectures on theta. I, Progress in Mathematics, vol. 28, Birkhäuser Boston, Inc., Boston, MA, 1983. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. MR 688651, DOI 10.1007/978-1-4899-2843-6
J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745–763. MR 1035941, DOI 10.1090/S0025-5718-1990-1035941-X
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578
É. Schost, Complexity results for triangular sets, J. Symbolic Comput. 36 (2003), 555–594.
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
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
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.