Algorithmes de recherche de racines sur les corps de fonctions de courbes algébriques

Exposé aux Journées Nationales de Calcul Formel, CIRM (Novembre 2005)

Nous proposons un algorithme pour trouver les racines d’un polynôme univarié à coefficients dans le corps de fonction d’une courbe algébrique (ou plus généralement dans un corps discrètement valué). Cette méthode peut être appliquée au décodage en liste des codes géométriques lors que la méthode de Newton-Hensel ne peut être utilisée.

A Newton-Puiseux root finding algorithm over function fields of curves (Preprint non publié, November 2005)

Soit k un corps parfait de caracteristique quelconque, X une courbe géométriquement irréductible définie sur k et K son corps de fonctions. Soit G un polynôme sur K et D un diviseur, nous proposons un algorithme pour trouver toutes les racines de G dans l’espace de Riemann-Roch L(D). Une application de cette méthode est l’étape de recherche de racines dans le décodage en liste des codes géométriques quand la très efficace méthode de Newton-Hensel ne peut être utilisée. Notre algorithme a deux étapes :
1.) utiliser une méthode de Newton-Puiseux, calculer suffisamment de termes des racines de l’image du polynôme dans un complété;
2.) en déduire les racines comme fonctions de L(D) en utilisant de l’algèbre linéaire sur k.
Nous généralisons cette méthode aux corps discrètement valués.