Root finding algorithms over function fields of algebraic curves

Talk at Journées Nationales de Calcul Formel, CIRM (November 2005)

We propose an algorithm to find the roots of a univariate polynomial with coefficients in the function field of an algebraic curve (or more generally, in a discretely valued field). This method can be applied to the list decoding of algebraic-geometric codes when the Newton-Hensel method can’t be used.

A Newton-Puiseux root finding algorithm over function fields of curves (Unpublished preprint, November 2005)

Let k be a perfect field of any characteristic, X a geometrically irreducible curve defined over k and K its function field. Given a polynomial G over K and a divisor D, we propose an algorithm to find all roots of G in the Riemann-Roch space L(D). An application of this method is the root finding step in list decoding of algebraic-geometric codes, when the very efficient Newton-Hensel method can’t be used. Our algorithm has two steps:
1.) using a Newton-Puiseux method, compute sufficiently many terms of the roots of the polynomial’s image into some completion;
2.) pull-back its roots as functions of L(D) using linear algebra over k.
We generalize this method to discretely valued fields.