Abstract
We are given a system of polynomial equations (say m equations of degree d each in n variables) over a (large) finite field F_p and we want to determine whether the system has a solution in that finite field (NOT in the algebraic closure). In other words, we want to determine if a polynomial system over a given finite field contains a rational point. We will see a deterministic algorithm for this problem whose running time is poly(m * d^n * log p). In particular, for any fixed value of n, the algorithm has running time polynomial in d, m and log p.