Mathematics of Computation

Author(s): P. Gaudry; É. Schost.
Journal: Math. Comp. 74 (2005), 429-454.
MSC (2000): Primary 11Y40; Secondary 11G20, 11Y16
Posted: May 25, 2004
Retrieve article in: PDF DVI PostScript

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.

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 , 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.

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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS