@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, dans Séminaire Bourbaki - Volume 2006/2007 - Exposés 967-981, Astérisque, no. 317 (2008), Exposé 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
[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
[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
[31] Équations différentielles à points singuliers réguliers, Springer, 1970, Lecture Notes in Mathematics, Vol. 163. | MR | Zbl
-
[32] Formes modulaires et représentations
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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]
[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
[102] The cohomology of Monsky and Washnitzer, Mém. Soc. Math. France N.S. (1986), p. 4, 33-59, Introductions aux cohomologies
[103] Point counting on genus
[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
[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
[112] Bessel
[113] Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. I Math. 273 (1971), p. 238-241. | MR | Zbl
-
[114] The
[115] Computing zeta functions of hyperelliptic curves over finite fields of characteristic
[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
-