Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-29T05:42:32.655Z Has data issue: false hasContentIssue false
  • English
  • Français

A Point Counting Algorithm Using Cohomology with Compact Support

Published online by Cambridge University Press:  01 February 2010

Gweltaz Chatel  and
David Lubicz
Gweltaz Chatel
Affiliation:
IRMAR, Université de Rennes 1, France, [email protected]
David Lubicz
Affiliation:
IRMAR, Université de Rennes 1, France, [email protected]

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.

We describe an algorithm to count the number of rational points of an hyperelliptic curve defined over a finite field of odd characteristic which is based upon the computation of the action of the Frobenius morphism on a basis of the Monsky-Washnitzer cohomology with compact support. This algorithm follows the vein of a systematic exploration of potential applications of cohomology theories to point counting.

Our algorithm decomposes in two steps. A first step which consists of the computation of a basis of the cohomology and then a second step to obtain a representation of the Frobenius morphism. We achieve a Õ(g4n3) time complexity and O(g3n3) memory complexity where g is the genus of the curve and n is the absolute degree of its base field. We give a detailed complexity analysis of the algorithm as well as a proof of correctness.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 12 , 2009 , pp. 295 - 325
Copyright
Copyright © London Mathematical Society 2009

References

1.Aho, A. V., Steiglitz, K. and Ullman, J. D., ‘Evaluating polynomials at fixed sets of points.’ SIAM J. Comput. 4 (1975) 533–539.CrossRefGoogle Scholar
2.Bostan, A., Chyzak, F., Ollivier, F., Salvy, B., Schost, É. and Sedoglavic, A., ‘Fast computation of power series solutions of systems of differential equations.’ ‘SODA,’ (2007) pp. 1012–1021.Google Scholar
3.Bostan, Alin, Salvy, Bruno and Schost, Éric, ‘Power series composition and change of basis.’ ‘ISSAC'08,’ (ed. Jeffrey, David J.) (ACM Press, To appear) Proceedings of ISSAC'08, Hagenberg, Austria.Google Scholar
4.Chatel, G., ‘Comptage de points : Application des méthodes cristallines.’ Thesis of the Université de Rennes1.Google Scholar
5.Chatel, G. and Lubicz, D., ‘Magma implementation of point counting algorithm using cohomology with compact support.’, (2008). Available at http://perso.univrennes1.fr/david.lubicz/programs/.Google Scholar
6.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
7.Corless, R. M., Gonnet, G. H., Hare, D. E. G., Jeffrey, D. J. and Knuth, D. E., ‘On the Lambert W function.’ Adv. Comput. Math. 5 (1996) 329–359.CrossRefGoogle Scholar
8.Dwork, Bernard, Generalized hypergeometric functions. Oxford Mathematical Monographs (The Clarendon Press Oxford University Press, New York, 1990). ISBN 0-19-853567-8. Oxford Science Publications.CrossRefGoogle Scholar
9.Dwork, Bernard, Gerotto, Giovanni and Sullivan, Francis J., An introduction to G-functions, vol. 133 of Annals of Mathematics Studies (Princeton University Press, Princeton, NJ, 1994). ISBN 0-691-03681-0.Google Scholar
10.Elkies, Noam D., ‘Elliptic and modular curves over finite fields and related computational issues.’ ‘Computational perspectives on number theory (Chicago, IL, 1995),’ (Amer. Math. Soc., Providence, RI, 1998), vol. 7 of AMS/IP Stud. Adv. Math. pp. 21–76.Google Scholar
11.Elkik, Renée, ‘Solutions d'équations à coefficients dans un anneau hensélien.’ Ann. Sci. École Norm. Sup. (4) 6 (1973) 553–603 (1974).CrossRefGoogle Scholar
12.Étesse, Jean-Yves and Stum, Bernard Le, ‘Fonctions L associées aux F-isocristaux surconvergents. I. Interprétation cohomologique.’ Math. Ann. 296 (1993) 557–576.CrossRefGoogle Scholar
13.Gaudry, Pierrick, ‘Algorithmique des courbes hyperelliptiques et applications à la cryptologie.’ Ph.D. thesis, École Polytechnique, (2000).Google Scholar
14.Gaudry, Pierrick, ‘Cardinality of a genus 2 hyperelliptic curve over GF(5. 1024 + 41).’ Email at the Number Theory List, (Sep. 2002).Google Scholar
15.Gaudry, Pierrick, ‘A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2.’ ‘Advances in cryptology—ASIACRYPT 2002,’ (Springer, Berlin, 2002), Lecture Notes in Comput. Sci.Google Scholar
16.Katz, Nicholas, ‘Travaux de Dwork.’ ‘Séminaire Bourbaki, 24ème année (1971/1972), Exp. No. 409,’ (Springer, Berlin, 1973) pp. 167–200. Lecture Notes in Math., Vol. 317.CrossRefGoogle Scholar
17.Kedlaya, K.S., ‘Counting points on hyperelliptic curves using Monsky Washnitzer cohomology.’ Journal of the Ramanujan Mathematical Society 16 (2001) 323–328.Google Scholar
18.Lauder, Alan G. B., ‘Deformation theory and the computation of zeta functions.’ Proc. London Math. Soc. (3) 88 (2004) 565–602.CrossRefGoogle Scholar
19.Lauder, Alan G. B., ‘A recursive method for computing zeta functions of varieties.’ LMS J. Comput. Math. 9 (2006) 222–269 (electronic).CrossRefGoogle Scholar
20.Lauder, Alan G. B. and Wan, Daqing, ‘Computing zeta functions of Artin-Schreier curves over finite fields.’ LMS J. Comput. Math. 5 (2002) 34–55 (electronic).CrossRefGoogle Scholar
21.Lauder, Alan G. B. and Wan, Daqing, ‘Computing zeta functions of Artin-Schreier curves over finite fields. II.’ J. Complexity 20 (2004) 331–349.CrossRefGoogle Scholar
22.Stum, Bernard Le, ‘Filtration par le poids sur la cohomologie de de Rham d'une courbe projective. Non Sesingulière sur un corps Unultramétrique complet.’. Rend. Sem. Mat. Padova 93 (1995) 43–85.Google Scholar
23.Lercier, R. and Lubicz, D., ‘Counting Points on Elliptic Curves over Finite Fields of Small Characteristic in Quasi Quadratic Time.’ ‘Advances in Cryptology—EUROCRYPT'2003’ (ed. Biham, Eli) (Springer-Verlag, 2003), Lecture Notes in Computer Science.Google Scholar
24.Lercier, Reynald and Lubicz, David, ‘A quasi quadratic time algorithm for hyperelliptic curve point counting.’ Ramanujan J. 12 (2006) 399–423.CrossRefGoogle Scholar
25.Mestre, Jean-François, ‘Lettre à Gaudry et Harley.’, (2001). Available at http://www.math.jussieu.fr/mestre.Google Scholar
26.Mestre, Jean-François, ‘Notes of a talk given at the seminar of cryptography of Rennes.’, (2002). Available at http://www.math.univ-rennes1.fr/crypto/2001-02/mestre.ps.Google Scholar
27.Papadimitriou, Christos H., Computational complexity (Addison-Wesley Publishing Company, Reading, MA, 1994). ISBN 0-201-53082-1.Google Scholar
28.Paterson, Michael S. and Stockmeyer, Larry J., ‘On the number of non-scalar multiplications necessary to evaluate polynomials.’ SIAM J. Comput. 2 (1973) 60–66.CrossRefGoogle Scholar
29.Pila, J., ‘Frobenius maps of abelian varieties and finding roots of unity in finite fields.’ Math. Comp. 55 (1990) 745–763.CrossRefGoogle Scholar
30.Robert, Alain M., A course in p-adic analysis, vol. 198 of Graduate Texts in Mathematics (Springer-Verlag, New York, 2000). ISBN 0-387-98669-3.CrossRefGoogle Scholar
31.Satoh, T., Skjernaa, B. and Taguchi, Y., ‘Fast computation of canonical lifts of elliptic curves and its application to point counting.’ Finite Fields and Their Applications 9 (2003) 89–101.CrossRefGoogle Scholar
32.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
33.Schoof, R., ‘Counting points on elliptic curves over finite fields.’ J. Théorie des nombres de Bordeaux 7 (1998) 483–494.Google Scholar
34.Tsuzuki, Nobuo, ‘On the Gysin isomorphism of rigid cohomology.’ Hiroshima Math. J. 29 (1999) 479–527.CrossRefGoogle Scholar
35.von zur Gathen, Joachim and Gerhard, Jürgen, Modern computer algebra (Cambridge University Press, Cambridge, 2003), 2nd edn. ISBN 0-521-82646-2.Google Scholar