@incollection{AST_2008__317__39_0, author = {Chambert-Loir, Antoine}, title = {Compter (rapidement) le nombre de solutions d'\'equations dans les corps finis}, booktitle = {S\'eminaire Bourbaki - Volume 2006/2007 - Expos\'es 967-981}, series = {Ast\'erisque}, note = {talk:968}, pages = {39--90}, publisher = {Soci\'et\'e math\'ematique de France}, number = {317}, year = {2008}, mrnumber = {2487730}, zbl = {1189.11059}, language = {fr}, url = {http://archive.numdam.org/item/AST_2008__317__39_0/} }
TY - CHAP AU - Chambert-Loir, Antoine TI - Compter (rapidement) le nombre de solutions d'équations dans les corps finis BT - Séminaire Bourbaki - Volume 2006/2007 - Exposés 967-981 AU - Collectif T3 - Astérisque N1 - talk:968 PY - 2008 SP - 39 EP - 90 IS - 317 PB - Société mathématique de France UR - http://archive.numdam.org/item/AST_2008__317__39_0/ LA - fr ID - AST_2008__317__39_0 ER -
%0 Book Section %A Chambert-Loir, Antoine %T Compter (rapidement) le nombre de solutions d'équations dans les corps finis %B Séminaire Bourbaki - Volume 2006/2007 - Exposés 967-981 %A Collectif %S Astérisque %Z talk:968 %D 2008 %P 39-90 %N 317 %I Société mathématique de France %U http://archive.numdam.org/item/AST_2008__317__39_0/ %G fr %F AST_2008__317__39_0
Chambert-Loir, Antoine. Compter (rapidement) le nombre de solutions d'équations dans les corps finis, in Séminaire Bourbaki - Volume 2006/2007 - Exposés 967-981, Astérisque, no. 317 (2008), Talk no. 968, 52 p. http://archive.numdam.org/item/AST_2008__317__39_0/
[1] Bounding Picard numbers of surfaces using p-adic cohomology, in Arithmetic, Geometry, and Coding Theory (AGCT-10), 2006, arXiv:math.NT/0601508. | MR | Zbl
, & -[2] Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, Springer, 1992. | MR | Zbl
& -[3] Counting points on curves and abelian varieties over finite fields, J. Symbolic Comput. 32 (2001), p. 171-189. | DOI | MR | Zbl
& ,[4] The number of points of an elliptic curve modulo a prime, 1988.
-[5] The number of points of an elliptic curve modulo a prime (II), 1992.
,[6] Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), p. 355-380. | DOI | MR | Zbl
-[7] Algebraic versus rigid cohomology with logarithmic coefficients, in Barsotti Symposium in Algebraic Geometry (Abano Terme, 1991), Perspect. Math., vol. 15, Académie Press, 1994, p. 11-50. | DOI | MR | Zbl
& -[8] Géométrie rigide et cohomologie des variétés algébriques de caractéristique p, Mém. Soc. Math. France (1986), p. 7-32, Introductions aux cohomologies p-adiques (Luminy, 1984). | DOI | EuDML | Numdam | MR | Zbl
-[9] Cohomologie rigide et cohomologie rigide à supports propres. Première partie, Prépublication, IRMAR, Université Rennes 1, 1996.
,[10] Dualité de Poincaré et formule de Kùnneth en cohomologie rigide, C. R. Acad. Sci. Paris Sér. I Math. 325 (1997), p. 493-498. | DOI | MR | Zbl
,[11] Finitude et pureté cohomologique en cohomologie rigide, Invent. Math. 128 (1997), p. 329-377, avec un appendice en anglais par A. J. de Jong. | DOI | MR | Zbl
,[12] Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, 2000, Reprint of the 1999 original. | MR | Zbl
, & -[13] Advances in elliptic curve cryptography, London Mathematical Society Lecture Note Series, vol. 317, Cambridge University Press, 2005. | Zbl
, & (éds.) -[14] On exponential sums in finite fields. II, Invent. Math. 47 (1978), p. 29-39. | DOI | EuDML | MR | Zbl
-[15] A rigid analytic version of M. Artin's theorem on analytic équations, Math. Ann. 255 (1981), p. 395-404. | DOI | EuDML | MR | Zbl
-[16] The Magma algebra System. I. The user language, J. Symbolic Comput. 24 (1997), p. 235-265, Computational algebra and number theory (London, 1993). | DOI | MR | Zbl
, & -[17] Moyenne arithmético-géométrique et périodes des courbes de genre 1 et 2, Gaz. Math. (1988), p. 36-64. | MR | Zbl
& -[18] Linear récurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM Journal on Computing 36 (2007), p. 1777-1806. | DOI | MR | Zbl
, & -[19] On the modularity of elliptic curves over : wild -adic exercises, Amer. J. Math. 14 (2001), p. 843-939. | DOI | MR | Zbl
, , & -[20] On the analogue of the division polynomials for hyperelliptic curves, J. reine angew. Math. 447 (1994), p. 91-145. | EuDML | MR | Zbl
-[21] A generalized arithmetico-geometric mean, Thèse, Rijksuniversiteit Groningen, 2004.
-[22] Canonical coordinates on the canonical lift, The Ramanujan Journal 22 (2007), p. 1-14, arXiv:math/0508007. | MR | Zbl
,[23] A -adic quasi-quadratic point counting algorithm, 2007, arXiv:math/0706.0234. | MR | Zbl
& -[24] Computing Zeta Functions of Nondegenerate Curves, 2006, arXiv:math.NT/0607308. | MR | Zbl
. & -[25] Weights in rigid cohomology applications to unipotent F-isocrystals, Ann. Sci. École Norm. Sup. 31 (1998), p. 683-715. | DOI | EuDML | Numdam | MR | Zbl
-[26] A comparison theorem for weights, J. reine angew. Math. 546 (2002), p. 159-176. | MR | Zbl
& -[27] A course in computational algebraic number theory, Graduate Texts in Mathématics, vol. 138, Springer, 1993. | MR | Zbl
-[28] Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. | MR | Zbl
, , , , , & (éds.) -[29] On the coefficients of the transformation polynomials for the elliptic modular function, Math. Proc. Cambridge Philos. Soc. 95 (1984), p. 389-402. | DOI | MR | Zbl
-[30] Computing -isogenies using the -torsion, in Algorithme number theory (Talence, 1996), Lecture Notes in Comput. Sci., vol. 1122, Springer, 1996, p. 59-65. | DOI | MR | Zbl
-[31] Équations différentielles à points singuliers réguliers, Springer, 1970, Lecture Notes in Mathematics, Vol. 163. | MR | Zbl
-[32] Formes modulaires et représentations -adiques, in Séminaire Bourbaki 1968/69, Lecture Notes in Math., 1971, Exp. 355, p. 139-172. | DOI | EuDML | Numdam | MR | Zbl
,[33] Théorie de Hodge II, Publ. Math. Inst. Hautes Études Sci. 40 (1971), p. 5-57. | DOI | EuDML | Numdam | MR | Zbl
,[34] La conjecture de Weil, I, Publ. Math. Inst. Hautes Études Sci. 43 (1974), p. 273-307. | DOI | EuDML | Numdam | MR | Zbl
,[35] Cohomologie étale (Séminaire de géométrie algébrique du Bois-Marie - SGA ), Lecture Notes in Mathematics, vol. 569, Springer, 1977, Avec la collaboration de , , et . | MR | Zbl
,[36] La conjecture de Weil, II, Publ. Math. Inst. Hautes Études Sci. 52 (1980), p. 137-252. | DOI | EuDML | Numdam | MR | Zbl
,[37] Counting points on curves using Monsky-Washnitzer cohomology, Finite Fields Appl. 12 (2006), p. 78-102. | DOI | MR | Zbl
& -[38] An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic 2, J. Cryptology 19 (2006), p. 1-25. | DOI | MR | Zbl
& ,[39] Die Typen der Multiplikatorringe elliptischer Funktionenkörper, Abh. Math. Sem. Hannsischen Univ. 14 (1941), p. 197-272. | DOI | JFM | MR
-[40] New directions in cryptography, IEEE Trans. Inform. Theory 22 (1976), p. 644-654. | DOI | MR | Zbl
& -[41] On the rationality of the zeta function of an algebraic variety, Amer. J. Math. 82 (1960), p. 631-648. | DOI | MR | Zbl
-[42] Canonical liftings of Jacobians, Compositio Math. 58 (1986), p. 111-131. | EuDML | Numdam | MR | Zbl
& -[43] Point counting after Kedlaya, EIDMA-Stieltjes Graduate course, Leiden, September 22-26, 2003, http://www.math.leidenuniv.nl/edix/oww/mathofcrypt/carls_edixhoven/kedlaya.pdf, 2003.
-[44] On the computation of coefficients of a modular form, Tech. report, 2006, arXiv:math.NT/0605244.
, , , & -[45] Explicit isogenies, 1991.
-[46] Solutions d'équations à coefficients dans un anneau hensélien, Ann. Sci. École Norm. Sup. 6 (1973), p. 553-603. | DOI | EuDML | Numdam | MR | Zbl
-[47] Computing modular polynomials in quasi-linear time, Prépublication, http://www.lix.polytechnique.fr/Labo/Andreas.Enge/vorabdrucke/modcomp.pdf, 2006. | Zbl
-[48] A new record for SEA, http://www.lix.polytechnique.fr/~morain/SEA/d2100x.annonce, 2006.
, & -[49] An extension of Satoh's algorithm and its implementation, J. Ramanujan Math. Soc. 15 (2000), p. 281-318. | MR | Zbl
, & -[50] Rigid analytic geometry and its applications, Progress in Mathematics, vol. 218, Birkhäuser, 2004. | MR | Zbl
& -[51] A remark concerning m-divisibility and the discrète logarithm problem in the divisor class group of curves, Math. Comp. 62 (1994), p. 865-874. | MR | Zbl
& -[52] Algebraic curves and cryptography, Finite Fields Appl. 11 (2005), p. 544-577. | DOI | MR | Zbl
& -[53] An extension of Kedlaya's point-counting algorithm to superelliptic curves, in Advances in cryptology-ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, 2001, p. 480-494. | DOI | MR | Zbl
& -[54] Counting points in médium characteristic using Kedlaya's algorithm, Experiment. Math. 12 (2003), p. 395-402. | DOI | EuDML | MR | Zbl
& ,[55] Counting points on hyperelliptic curves over finite fields, in Algorithmic number theory (Leiden, 2000), Lecture Notes in Comput. Sci., vol. 1838, Springer, 2000, p. 313-332. | DOI | MR | Zbl
& -[56] Relative rigid cohomology and point counting in families of elliptic curves, 2005, http://joguinf.informatik.uni-mainz.de/~gerkmann/legendre.pdf. | Zbl
-[57] Primality testing using elliptic curves, J. ACM 46 (1999), p. 450-472. | DOI | MR | Zbl
& -[58] On the de Rham cohomology of algebraic varieties, Publ. Math. I.H.É.S. (1966), p. 95-103. | DOI | EuDML | Numdam | MR | Zbl
-[59] Cohomologie -adique et fonctions , Lecture Notes in Math., Springer, 1972-73, SGA 5.
,[60] Formule de Lefschetz et rationalité des fonctions L, in Séminaire Bourbaki, Vol. 9, Soc. Math. France, 1995, Exp. No. 279, Année 1964-1965, p. 41-55. | EuDML | Numdam | MR | Zbl
,[61] Asymptotically optimal -adic point-counting, e-mail à la liste NMBRTHRY, décembre 2002.
-[62] Kedlaya's Algorithm in Larger Characteristic, Internat. Math. Res. Notices (2006), à paraître, arXiv:math.NT/0610973. | MR | Zbl
-[63] Beweis des Analogons der Riemannschen Vermutung für die Artinschen und F. K. Schmidtschen Kongruenzzetafunktionen in gewissen elliptischen Fällen. Vorläufige Mitteilung, Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse 42 (1933), p. 253-262, http://gdzdoc.sub.uni-goettingen.de/sub/digbib/loader?did=D64289. | EuDML | JFM | Zbl
-[64] Zur Théorie der abstrakten elliptischen Funktionenkörper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung., J. reine angew. Math. 175 (1936), p. 193-208, http://gdzdoc.sub.uni-goettingen.de/sub/digbib/loader?did=D255900. | EuDML | JFM | MR | Zbl
,[65] Integrais of the second kind on an algebraic variety, Ann. of Math. 62 (1955), p. 56-91. | DOI | MR | Zbl
& -[66] Memory efficient hyperelliptic curve point counting, 2006, arXiv:math. NT/0609032. | MR | Zbl
-[67] Point counting in families of hyperelliptic curves, 2006, arXiv:math.NT/0601438. | MR | Zbl
,[68] Point counting in families of hyperelliptic curves in characteristic , 2006, arXiv:math.NT/0607346. | MR | Zbl
,[69] Zeta matrices of elliptic curves, J. Number Theory 15 (1982), p. 318-330. | DOI | MR | Zbl
& -[70] Some consequences of the Riemann hypothesis for varieties over finite fields, Invent. Math. 23 (1974), p. 73-77. | DOI | EuDML | MR | Zbl
& -[71] Counting points on hyperelliptic curves using Monsky- Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), p. 323-338, | MR | Zbl
-Counting points on hyperelliptic curves using Monsky- Washnitzer cohomology, Erratum : J. Ramanujan Math. Soc. 18 (2003), no. 4, 417-418. | MR | Zbl
-[72] Finiteness of rigid cohomology with coefficients, Duke Math. J. 134 (2006), p. 15-97. | DOI | MR | Zbl
,[73] A survey of public-key cryptosystems, SIAM Rev. 46 (2004), p. 599-634. | DOI | MR | Zbl
& -[74] The Heegner point lifting algorithm and elliptic curve point counting, in Advances in cryptology-ASIACRYPT 2003, Lecture Notes in Comput. Sci., vol. 2894, Springer, 2003, p. 124-136. | DOI | MR | Zbl
-[75] Deformation theory and the computation of zeta functions, Proc. London Math. Soc. 88 (2004), p. 565-602. | DOI | MR | Zbl
-[76] Rigid cohomology and -adic point counting, J. Théor. Nombres Bordeaux 17 (2005), p. 169-180. | DOI | EuDML | Numdam | MR | Zbl
,[77] A recursive method for Computing zeta functions of varieties, LMS J. Comp. Math. 9 (2006), p. 222-267, http://www.lms.ac.uk/jcm/9/lms2006-005. | DOI | MR | Zbl
,[78] Counting points on varieties over finite fields of small characteristic, in Algorithmic Number Theory : Lattices, Number Fields, Curves and Cryptography (J. Buhler & P. Stevenhagen, éds.), Mathematical Sciences Research Institute Publications, Cambridge University Press, 2007, à paraître, http://www.maths.ox.ac.uk/. | Zbl
& -[79] A course on rigid cohomology, Cambridge Tracts in Mathematics, Cambridge Univ. Press, 2007, à paraître. | MR | Zbl
-[80] Computing isogenies in , in Algorithmic number theory (Talence, 1996), Lecture Notes in Comput. Sci., vol. 1122, Springer, 1996, p. 197-212. | DOI | MR | Zbl
-[81] Counting points in elliptic curves over finite fields of small characteristic in quasi quadratic time, in Advances in cryptology- EUROCRYPT 2003, Lecture Notes in Comput. Sci., vol. 2656, Springer, 2003, p. 360-373. | DOI | MR | Zbl
& -[82] A Quasi Quadratic Time Algorithm for Hyperelliptic Curve Point Counting, The Ramanujan Journal 12 (2006), p. 399-423, http://medicis.polytechnique.fr/~lercier/file/LL05.pdf. | DOI | MR | Zbl
& ,[83] Computing isogenies between elliptic curves over using Couveignes's algorithm, Math. Comp. 69 (2000), p. 351-370. | DOI | MR | Zbl
& -[84] Elliptic curves and formai groups, 1964, Lecture notes prepared in connection with the seminars held at the Summer institute on Algebraic Geometry, Whitney State, Woods Hole, Massachusetts, http://ma.utexas.edu/users/voloch/lst.html.
, & -[85] The relationship between breaking the Diffie- Hellman protocol and Computing discrète logarithms, SIAM J. Comput. 28 (1999), p. 1689-1721. | DOI | MR | Zbl
& -[86] Sur le théorème de finitude de la cohomologie -adique d'une variété affine non singulière, Amer. J. Math. 119 (1997), p. 1027-1081. | DOI | MR | Zbl
-[87] The crystals associated to Barsotti-Tate groups : with applications to abelian schemes, Lecture Notes in Math., Springer, 1976. | MR | Zbl
-[88] Utilisation de l'AGM pour le calcul de , Lettre à Harley et Gaudry, décembre 2000, http://www.math.jussieu.fr/~mestre.
-[89] Algorithmes pour compter des points de courbes en petite caractéristique et en petit genre, rédigé par David Lubicz, http://www.math.jussieu.fr/~mestre/rennescrypto.ps, 2002.
,[90] Formal cohomology I, Ann. of Math. 88 (1968), p. 181-217. | DOI | MR | Zbl
& -[91] Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), p. 255-282, Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). | DOI | EuDML | Numdam | MR | Zbl
-[92] La primalité en temps polynomial (d'après Adleman, Huang ; Agrawal, Kayal, Saxena), Astérisque (2004), p. 205-230. | EuDML | Numdam | MR | Zbl
,[93] Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik gröfier drei, Thèse, University of Saarland, Saarbrücken, 1995.
-[94] Tata lectures on Thêta II, Birkhäuser, 1984. | MR | Zbl
-[95] The equivalence between the DHP and DLP for elliptic curves used in practical applications, LMS J. Comput. Math. 7 (2004), p. 50-72. | DOI | MR | Zbl
, & -[96] L'algorithme de Cornacchia, Exposition. Math. 13 (1995), p. 358-365. | MR | Zbl
-[97] , version 2.3.1, 2006, http://pari.math.u-bordeaux.fr/.
-[98] Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), p. 745-763. | DOI | MR | Zbl
-[99] Counting points on curves over families in polynomial time, 1991, arXiv:math.NT/0504570.
,[100] An improved algorithm for Computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Information Theory IT-24 (1978), p. 106-110. | DOI | MR | Zbl
& -[101] Monte Carlo methods for index computation (mod ), Math. Comp. 32 (1978), p. 918-924. | MR | Zbl
-[102] The cohomology of Monsky and Washnitzer, Mém. Soc. Math. France N.S. (1986), p. 4, 33-59, Introductions aux cohomologies -adiques (Luminy, 1984). | EuDML | Numdam | MR | Zbl
-[103] Point counting on genus non hyperelliptic curves, in Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, 2004, p. 379-394. | DOI | MR | Zbl
-[104] The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), p. 247-270. | MR | Zbl
-[105] Fast computation of canonical lifts of elliptic curves and its application to point counting, Finite Fields Appl. 9 (2003), p. 89-101. | DOI | MR | Zbl
, & -[106] Elliptic curves over finite fields and the computation of square roots mod , Math. Comp. 44 (1985), p. 483-494. | MR | Zbl
-[107] Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), p. 219-254, Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). | DOI | EuDML | Numdam | MR | Zbl
,[108] Class number, a theory of factorization, and genera, in 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969), Amer. Math. Soc., 1971, p. 415-440. | MR | Zbl
-[109] Crystalline fundamental groups. II Log convergent cohomology and rigid cohomology, J. Math. Sci. Univ. Tokyo 9 (2002), p. 1-163. | MR | Zbl
-[110] Lower bounds for discrète logarithms and related problems, in Advances in cryptology-EUROCRYPT '97, Lecture Notes in Comput. Sci., vol. 1233, Springer, 1997, p. 256-266. | MR
-[111] Satoh's algorithm in characteristic , Math. Comp. 72 (2003), p. 477-487. | DOI | MR | Zbl
-[112] Bessel -isocrystals and an algorithm for Computing Kloosterman sums, 2003.
-[113] Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. I Math. 273 (1971), p. 238-241. | MR | Zbl
-[114] The algorithm in characteristic , http://homes.esat.kuleuven.be/~fvercaut/papers/SEA.pdf.gz, 2000.
-[115] Computing zeta functions of hyperelliptic curves over finite fields of characteristic , in Advances in cryptology-CRYPTO 2002, Lecture Notes in Comput. Sci., vol. 2442, Springer, 2002, p. 369-384. | DOI | MR | Zbl
,[116] A memory efficient version of Satoh's algorithm, in Advances in cryptology-EUROCRYPT 2001 (Innsbruck), Lecture Notes in Comput. Sci., vol. 2045, Springer, 2001, p. 1-13. | DOI | MR | Zbl
, & -[117] Algorithmic theory of zeta functions over finite fields, in Algorithmic Number Theory : Lattices, Number Fields, Curves and Cryptography (J. Buhler & P. Stevenhagen, éds.), Mathematical Sciences Research Institute Publications, Cambridge University Press, 2007, à paraître, http://www.maths.ox.ac.uk/. | MR | Zbl
-[118] Abelian varieties over finite fields, Ann. Sci. Ecole Norm. Sup. 2 (1969), p. 521-560, http://www.numdam.org/item?id=ASENS_1969_4_2_4_521_0. | DOI | EuDML | Numdam | MR | Zbl
-[119] Variétés abéliennes et courbes algébriques, Actualités Sci. Ind., Hermann & Cie., Paris, 1948. | MR | Zbl
-