Séminaire de Cryptographie

Accueil     Présentation     Archives

François-Renaud Escriva


Calculs de cup-produits et comptage de points.

Dans cet exposé, nous présentons un algorithme de comptage de points qui repose sur le calcul de certains cup-produits. Notre algorithme se fonde, comme l'algorithme de Kedlaya, sur le calcul de la matrice de l'action d'un Frobenius semi-linéaire sur le premier groupe de cohomologie d'une courbe. Cependant, notre algorithme a l'avantage de pouvoir s'appliquer à une classe très générale de courbes. Pour ce faire, nous avons introduit trois nouvelles techniques : - une procédure pour calculer explicitement des relèvements du Frobenius relatif en toute généralité, - le calcul de la matrice du Frobenius au moyen de calculs de résidus, ce qui évite des manipulations généralement coûteuses de 1-formes, - une technique de relèvement local du Frobenius pour améliorer la performance de notre algorithme. Ce travail a été réalisé en collaboration avec Amnon Besser et Rob de Jeu.