Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1991 Copyright 1991 Universität Bonn, Institut für Informatik, Abt. V
8565

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]
Dima Grigoriev, Marek Karpinski
[Download PostScript] [Download PDF]

We design the first polynomial time (for an arbitrary and fixed field $GF[q]$) $(\eps,\delta)$-approximation algorithm for the number of zeros of arbitrary polynomial $f(x_1, \ldots, 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 (cf. \cite{BS90}). The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial $f(x_1, \ldots , x_n)$ over $GF[q]$ in the function on the number $m$ of its terms. The bounding ratio number is proved to be $m^{(q-1) \log q}$ which is the main technical contribution of this paper and could be of independent algebraic interest.

Last Change: 11/05/14 at 09:38:33
 English
Universität Bonn -> Institut für Informatik -> Abteilung V