Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Solvability of a System of Bivariate Polynomial Equations over a Finite Field

Neeraj Kayal

Abstract

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.

Details

Publication typeInproceedings
Published inInternational Colloquium on Automata, Languages and Programming (ICALP)
URLhttp://dx.doi.org/10.1007/11523468_45
Pages551–562
Volume3580
SeriesLecture Notes in Computer Science
ISBN3-540-27580-0
PublisherSpringer
> Publications > Solvability of a System of Bivariate Polynomial Equations over a Finite Field