Abstract:
We give new randomized algorithms for testing multivariate polynomial identities over finite fields and rationals. The algorithms use \lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil in case of rationals where C is the largest coefficient) random bits to test if a polynomial P(x_1, ..., x_n) is zero where d_i is the degree of x_i in P and has an error probability of \epsilon for any \epsilon > 0. The running time of the algorithms is polynomial in the size of arithmetic circuit representing the input polynomial and 1/\epsilon. These algorithms use fewer random bits than all the known methods and also take an order of magnitude less time compared to some of the recently proposed methods [Chen-Kao, Lewin-Vadhan]. Our algorithms first transform the input polynomial to a univariate polynomial and then uses Chinese remaindering over univariate polynomials to efficiently test if it is zero. We also give a simple test for primality based on identity checking.