TR99-018 Authors: Manindra Agrawal, Somenath Biswas

Publication: 8th June 1999 17:56

Downloads: 1690

Keywords:

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.