Comptage de points : application des méthodes cristallines
Institution:
Rennes 1Disciplines:
Directors:
Abstract EN:
We deal in this thesis with the computation of the number of points of algebraic curves over finite fields. By use of the stability of the rigid cohomology with compact support by finite etale descent, we show that the computation of the cohomology groups of such a curve can be reduced to the computation of the cohomology groups of an isocrystal over an open subset of the affine line and we build an algorithm achieving this operation in polynomial time. We then show that using a lifting of Frobenius for an algebraic curve over a finite field computed thanks to an algorithm presented by Gerkmann in his thesis, we can count the number of points of the curve by application of the trace formula for rigid cohomology, finally obtaining a polynomial time algorithm working for a large class of curves. We furthermore find complexities for our algorithms, using some technics introduced by Lauder in order to control the absolute value of the elements of the cohomology basis we handle.
Abstract FR:
On s’intéresse dans cette thèse au calcul du nombre de points de courbes algébriques sur des corps finis. En utilisant la stabilité de la cohomologie rigide à support propre par descente finie étale, on montre que l’on peut ramener le calcul des groupes de cohomologie d’une telle courbe à celui des groupes de cohomologie d’un isocristal sur un ouvert de la droite affine, et on construit un algorithme effectuant ce calcul en temps polynomial. On montre alors qu’en utilisant un relevé de Frobenius pour une courbe algébrique sur un corps fini calculé à l’aide d’un algorithme présenté par Gerkmann dans sa thèse, on peut compter le nombre de points de la courbe en appliquant la formule des traces en cohomologie rigide, obtenant finalement un algorithme polynomial fonctionnant pour une large classe de courbes. On détermine de plus des complexités pour nos algorithmes, recourant pour cela à des méthodes dues à Lauder pour contrôler la valeur absolue des éléments de la base de cohomologie que l’on manipule.