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

摘要

We investigate the complexity of the following polynomial solvability problem: Given a finite field F_q and a set of polynomials f_1(x,y),f_2(x,y), ··· , f_n(x,y), g(x,y) ∈ F_q [x, y] determine the F_q-solvability of the system f_1(x,y) = f_2(x,y) = ··· = f_n(x,y) = 0 and g(x,y) ≠ 0 We give a deterministic polynomial-time algorithm for this problem.