Checking Polynomial Identities over any Field: Towards a Derandomization?

Abstract

We present a Monte Carlo algorithm for testing multivariate polynomial identities over any field using fewer random bits than other methods. To test if a polynomial (P(x_1, ..., x_n)) is zero, our method uses (\sum_{i=1}^n \log \lceil d_i+1 \rceil) random bits, where (d_i) is the degree of (x_i) in (P), to obtain any inverse polynomial error in polynomial time. The algorithm applies to polynomials given as a black box or in some implicit representation such as a straight-line program. Our method works by evaluating P at truncated formal power series representing square roots of irreducible polynomials over the field. This approach is similar to that of Chen and Kao (STOC '97), but with the advantage that the techniques are purely algebraic and apply to any field. We also prove a lower bound showing that the number of random bits used by our algorithm is essentially optimal in the black-box model.