Séminaire de Cryptographie

Accueil     Présentation     Archives

Gweltaz Chatel


Comptage de points : application des méthodes cristallines

On présente une nouvelle méthode pour le 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 déterminé par un procédé décrit 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 à support, 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.