Solvability of a System of Bivariate Polynomial Equations over a Finite Field

We study the following problem - given a finite field F and a set of polynomials p1(x), p2(x), ... , pm(x) in n variables x=(x1, ..., xn) over F, determine if the corresponding system of equations

p1(x) = p2(x) = ... = pm(x) = 0

has a solution over F or not. We investigate the complexity of this problem when the number of variables is bounded. We show that for any fixed value of n, there is a deterministic algorithm for deciding solvability whose running time is bounded by a polynomial in d, m and log |F|. Previously, only a randomized polynomial-time algorithm was known (Huang and Wong, FOCS 1996). In particular, this result also leads to a deterministic algorithm for recognizing permutation functions, a problem which was previously known to be in ZPP (Ma and Gathen, STOC 1994) but not known to be in P.

chapters five and six.pdf
PDF file

In  International Colloquium on Automata, Languages and Programming (ICALP)

Publisher  Springer

Details

TypeInproceedings
URLhttp://dx.doi.org/10.1007/11523468_45
Pages551–562
Volume3580
SeriesLecture Notes in Computer Science
ISBN3-540-27580-0
> Publications > Solvability of a System of Bivariate Polynomial Equations over a Finite Field