Counting (quickly) the number of solutions of equations in finite fields. (Compter (rapidement) le nombre de solutions - d’équations dans les corps finis.) (French) Zbl 1189.11059

Séminaire Bourbaki. Volume 2006/2007. Exposés 967–981. Paris: Société Mathématique de France (ISBN 978-2-85629-253-2/pbk). Astérisque 317, 39-90, Exp. No. 968 (2008).
This is a very nice survey on algorithms for counting the number of points of varieties (mostly curves) over finite fields. After a brief account on possible applications (primality test, computation of square roots modulo \(p\), and discrete logarithm problem in cryptography), the author gives, using his own words, the point of view of ‘a pure mathematician suddenly interested in this applied mathematical problem’. This is indeed an excellent source for anyone interested in the main ideas behind the algorithms. These are divided into two categories:
1) \(\ell\)-adic approach with R. Schoof’s algorithm [Math. Comput. 44, 483–494 (1985; Zbl 0579.14025)] for elliptic curves, its improvements by Atkin and Elkies [see F. Morain, J. Théor. Nombres Bordeaux. 7, No. 1, 255–282 (1995; Zbl 0843.11030)] and its generalizations for abelian varieties and higher genus curves [L. M. Adleman and M.-D. Huang, J. Symb. Comput. 32, No. 3, 171–189 (2001; Zbl 0986.11039)].
2) \(p\)-adic methods using Dwork’s work [A. G. B. Lauder and D. Wan, in: Buhler, J. P. (ed.) et al., Algorithmic number theory. Lattices, number fields, curves and cryptography. Cambridge: Cambridge University Press. Mathematical Sciences Research Institute Publications 44, 579–612 (2008; Zbl 1188.11069)]; the canonical lift for elliptic curves [T. Satoh, J. Ramanujan Math. Soc. 15, No. 4, 247–270 (2000; Zbl 1009.11051)], its variants (Mestre’s AGM method for \(p=2\)) and generalizations to hyperelliptic curves [R. Lercier and D. Lubicz, Ramanujan J. 12, No. 3, 399–423 (2006; Zbl 1166.11021)], genus \(3\) non hyperelliptic curves [C. Ritzenthaler, in: Buell, Duncan (ed.), Algorithmic number theory. 6th international symposium, ANTS-VI, Burlington, VT, USA, June 13–18, 2004. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 3076, 379–394 (2004; Zbl 1125.11331)] and more recently \(p \neq 2\) [R. Carls and D. Lubicz, Int. Math. Res. Not. 2009, No. 4, 698–735 (2009; Zbl 1160.11034)]; Monsky-Washnitzer cohomology [K. S. Kedlaya, J. Ramanujan Math. Soc. 16, No. 4, 323–338 (2001; Zbl 1066.14024)]; deformation theory [A. G. B. Lauder, Proc. Lond. Math. Soc. (3) 88, No. 3, 565–602 (2004; Zbl 1119.11053)].
Let us also mention very recent work by H. Hubrechts [J. Symb. Comput. 44, No. 9, 1255–267 (2009; Zbl 1221.14025)] using rigid cohomology. For more details on implementations of \(p\)-adic algorithms we can advice to look at Frederik Vercauteren’s PhD [Computing zeta functions of curves over finite fields. PhD thesis, Katholieke Universiteit Leuven, November 2003].
For the entire collection see [Zbl 1151.00015].


11Y16 Number-theoretic algorithms; complexity
14G15 Finite ground fields in algebraic geometry
11D45 Counting solutions of Diophantine equations
14G40 Arithmetic varieties and schemes; Arakelov theory; heights
14F20 Étale and other Grothendieck topologies and (co)homologies
14F30 \(p\)-adic cohomology, crystalline cohomology
11G20 Curves over finite and local fields
11G25 Varieties over finite and local fields
Full Text: arXiv Link