January 22, 2019, 13h30. Aude Le gluher (Université de Lorraine, CNRS, INRIA.)

Place : LIX, Salle Henri Poincaré.

Title : Un algorithme géométrique efficace pour le calcul d’espaces de Riemann-Roch.

Abstract : Le calcul effectif de bases d’espaces de Riemann-Roch intervient dans de
nombreux domaines pratiques, notamment pour l’arithmétique dans les jacobiennes
de courbes ou pour la construction de codes correcteurs d’erreurs
algébraico-géométriques. Nous proposons une variante probabiliste de type Las
Vegas de l’algorithme de Brill et Noether décrit par Goppa pour le calcul d’une
base de l’espace de Riemann-Roch L(D) associé à un diviseur D sur une courbe
plane projective C de degré d définie sur un corps parfait K suffisamment
grand. On prouve que sa complexité (estimée par le nombre d’opérations
arithmétiques dans le corps K) est en O(max(d^(2 \omega), deg(D_+)^(\omega)))
où \omega est la constante de l’algèbre linéaire et D_+ est le plus petit
diviseur effectif supérieur ou égal à D. Cet algorithme probabiliste peut
échouer, mais sous quelques conditions on prouve que sa probabilité d’échec est
bornée par O(max(d^4,deg(D_+)^2)/|E|) où E est un sous ensemble fini de K dans
lequel on peut choisir des éléments de K uniformément aléatoirement. Nous avons
implémenté cet algorithme en C++/NTL et nous présenterons des résultats
expérimentaux qui semblent indiquer une amélioration des temps de calculs par
rapport à l’implémentation dans le logiciel de calcul formel Magma.

Travail commun avec Pierre-Jean Spaenlehauer.

Comments are closed.