Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-26T07:39:51.377Z Has data issue: false hasContentIssue false
  • English
  • Français

Point Counting in Families of Hyperelliptic Curves in Characteristic 2

Published online by Cambridge University Press:  01 February 2010

Hendrik Hubrechts
Hendrik Hubrechts
Affiliation:
Department of Mathematics, Katholieke Universiteit Leuven, Celestijnenlaan 200B - bus 2400, 3001 Leuven, Belgium, [email protected], http://wis.kuleuven.be/algebra/hubrechts/

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let EΓ be a family of hyperelliptic curves over F2alg cl with general Weierstrass equation given over a very small field F. The author of this paper describes an algorithm for computing the zeta function of Eγ, with γ in a degree n extension field of F, which has time complexity O(n3 + ε) bit operations and memory requirements O(n2) bits. Using a slightly different algorithm, one can get time O(n2.667) and memory O(n2.5), and the computation for n curves of the family can be done in time O(n3.376). All of these algorithms are polynomial-time in the genus.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 10 , 2007 , pp. 207 - 234
Copyright
Copyright © London Mathematical Society 2007

References

1.Bernstein, Daniel J., ‘Fast multiplication and its applications’, http://cr.yp.to/papers.html#multapps, to appear in Algorithmic number theory, ed Buhler, J. and Stevenhagen, P..Google Scholar
2.Castryck, W., Denef, J. and Vercauteren, F., ‘Computing zeta functions of nondegenerate curves.’ IMRP Int. Math. Res. Pap. (2006) Art. ID 72017, 57.Google Scholar
3.Chambert-Loir, Antoine, ‘Compter (rapidement) le nombre de solutions d'equations dans les corps finis’, Séminaire Bourbaki, 59e année, Novembre 2006.Google Scholar
4.Cohen, Henri, Frey, Gerhard, Avanzi, Roberto, Doche, Christophe, Lange, Tanja, Nguyen, Kim and Vercauteren, Frederik(eds), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications, Boca Raton (Chapman & Hall/CRC, Boca Raton, FL, 2006) ISBN 978-1-58488-518-4; 1-58488-518-1.Google Scholar
5.Coppersmith, Don and Winograd, Shmuel, ‘Matrix multiplication via arithmetic progressions’, J. Symbolic Comput. 9 (1990) 251–280.CrossRefGoogle Scholar
6.Denef, Jan and Vercauteren, Frederik, ‘An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic 2’, J. Cryptology 19 (2006) 1–25.Erratum available as [7].CrossRefGoogle Scholar
7.Denef, Jan and Vercauteren, Frederik, Errata for [6] and related papers,http://wis.kuleuven.be/algebra/denefpapers/ErrataPointCounting.pdf.Google Scholar
8.Elkies, Noam D., ‘Elliptic and modular curves over finite fields and related computational issues’, Computational perspectives on number theory, Chicago, IL, 1995, AMS/IP Stud. Adv. Math. 7 (Amer. Math. Soc, Providence, RI, 1998) 21–76.CrossRefGoogle Scholar
9.von zur Gathen, Joachim and Gerhard, Jürgen, Modern computer algebra (Cambridge University Press, Cambridge, 2003), ISBN 0-521-82646-2.207.Google Scholar
10.Gaudry, Pierrick and Harley, Robert, ‘Counting points on hyperelliptic curves over finite fields’, Algorithmic number theory, Leiden, 2000, Lecture Notes in Comput. Sci. 1838 (Springer, Berlin, 2000) 313–332.CrossRefGoogle Scholar
11.Gerkmann, Ralf, ‘Relative rigid cohomology and deformation of hypersurfaces’, Internat. Math. Research Papers., to appear.Google Scholar
12.Gerkmann, Ralf, ‘Relative rigid cohomology and point counting on families of elliptic curves’, Preprint, http://www.mathematik.uni-mainz.de/~gerkmann/.Google Scholar
13.Hubrechts, Hendrik, ‘Point counting in families of hyperelliptic curves’, Foundations of Computational Mathematics, to appear.Google Scholar
14.Kedlaya, Kiran S., ‘Counting points on hyperelliptic curves using Monsky- Washnitzer cohomology’, J. Ramanujan Math. Soc. 16 (2001) 323–338.Google Scholar
15.Kim, H. Y., Park, J. Y., Cheon, J. H., Park, J. H., Kim, J. H. and Hahn, S. G., ‘Fast elliptic curve point counting using Gaussian normal basis’, Algorithmic Number Theory Symposium - ANTS V, Lecture Notes in Computer Science 2369 (2002) 292–307.CrossRefGoogle Scholar
16.Lauder, Alan G.B., ‘Deformation theory and the computation of zeta functions’, Proc. London Math. Soc. (3) 88 (2004) 565–602.CrossRefGoogle Scholar
17.Lauder, Alan G.B., ‘Rigid cohomology and p-adic point counting’, J.Theor. Nombres Bordeaux 17 (2005) 169–180.CrossRefGoogle Scholar
18.Lauder, Alan G.B., ‘A recursive method for computing zeta functions of varieties’, LMS J. Gomput. Math. 9 (2006) 222–269, http://www.lms.ac.uk/jcm/9/lms2006-005.CrossRefGoogle Scholar
19.Satoh, Takakazu, ‘The canonical lift of an ordinary elliptic curve over a finite field and its point counting’, J. Ramanujan Math. Soc. 15 (2000) 247–270.Google Scholar
20.Shoup, Victor, ‘Efficient computation of minimal polynomials in algebraic extension of finite fields’, Proc. 1999 International Symposium on Symbolic and Algebraic Computation (ed. Dooley, S, ACM Press, New York, 1999).Google Scholar
21.Tsuzuki, N., ‘Bessel F-isocrystals and an algorithm of computing Kloosterman sums’, Preprint, 2003.Google Scholar
22.Vercauteren, Frederik, ‘Computing zeta functions of curves over finite fields, PhD thesis, KULeuven, Belgium, 2003.Google Scholar
23.Villard, Gilles, ‘Computation of the inverse and determinant of a matrix’, Algorithm Seminar 2001–2002 (ed. Chyzak, F., INRIA, 2003) 29–32.Google Scholar