Checking Polynomial Identities over any Field: Towards a Derandomization?

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 ; : : : ; xn ) is zero, our method uses P n i=1 dlog(d i + 1)e 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 [CK97], 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. 1 Introduction Checking multivariate polynomial identities of the form P 1 (x 1 ; : : : ; xn ) = P 2 (x 1 ;..