An approximation algorithm for the number of zeros or arbitrary polynomials over GF[q]

The authors design the first polynomial time (for an arbitrary and fixed field GF[q]) (∈, δ)-approximation algorithm for the number of zeros of arbitrary polynomial f(x₁. . . x_n) over GF[q]. It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF[2] (like GF[3]), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x₁. . ., x_n) over GF[q] in the function of the number m of its terms. The bounding ratio is proved to be m^(q-1)log^q