The computation of rational solutions of polynomial systems over a finite field

GUILLERMO MATERA

Castro Urdiales

Conferencia; VII Jornadas de Matemática Discreta y Algorítmica; 2010

Centro Internacional de Encuentros Matemáticos

We describe a family of probabilistic algorithms which compute a rational solution of a system of polynomial equations defined over a finite field Fq. We express their cost in terms of numerical invariants associated to the geometry of the solution set and discuss the cases where the answer is not satisfactory. The exposition is divided in three parts: first we consider bivariate equations, then we discuss multivariate equations and finally we analyze the general case of multivariate systems of polynomial equations.