Reynald Lercier

R. Lercier et D. Lubicz. A Quasi Quadratic Time Algorithm for Hyperelliptic Curve Point Counting. The Ramanujan Journal, 12(3):399-423, Décembre 2006.

Nous décrivons un algorithme pour calculer la cardinalité de jacobiennes de courbes hyperelliptiques ordinaires de petit genre définies sur des corps finis GF(2ⁿ) avec complexité O(n^2+o(1)). Cet algorithme dérive d'idées dues à Mestre. Plus précisément, nous donnons les éléments mathématiques derrière l'algorithme de Mestre et développons à partir de celui-ci une variante avec complexité quasi-quadratique. Entre autres choses, nous présentons un algorithme pour trouver les racines d'un système d'équations d'Artin-Schreier généralisées et donnons les résultats que nous obtenons avec une implantation efficace. En particulier, nous avons pu calculer la cardinalité de courbes de genre un, deux ou trois définies sur des corps finis de taille gigantesque.

[ bib | preprint | publication ] Retour