Paper detail

Compter (rapidement) le nombre de solutions d'équations dans les corps finis

The number of solutions in finite fields of a system of polynomial equations obeys a very strong regularity, reflected for example by the rationality of the zeta function of an algebraic variety defined over a finite field, or the modularity of Hasse-Weil's $L$-function of an elliptic curve over $\Q$. Since two decades, efficient methods have been invented to compute effectively this number of solutions, notably in view of cryptographic applications. This exposé presents some of these methods, generally relying on the use of Lefshetz's trace formula in an adequate cohomology theory and discusses their respective advantages. ----- Le nombre de solutions dans les corps finis d'un système d'équations polynomiales obéit à une très forte régularité, reflétée par exemple par la rationalité de la fonction zêta d'une variété algébrique sur un corps fini, ou la modularité de la fonction $L$ de Hasse-Weil d'une courbe elliptique sur $\Q$. Depuis une vingtaine d'années des méthodes efficaces ont été inventées pour calculer effectivement ce nombre de solutions, notamment en vue d'applications à la cryptographie. L'exposé en présentera quelques-unes, généralement fondées l'utilisation de la formule des traces de Lefschetz dans une théorie cohomologique convenable, et expliquera leurs avantages respectifs.