ECCC-Report TR99-018https://eccc.weizmann.ac.il/report/1999/018Comments and Revisions published for TR99-018en-usTue, 08 Jun 1999 17:56:33 +0300
Paper TR99-018
| Reducing Randomness via Chinese Remaindering |
Manindra Agrawal,
Somenath Biswas
https://eccc.weizmann.ac.il/report/1999/018
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.
Tue, 08 Jun 1999 17:56:33 +0300https://eccc.weizmann.ac.il/report/1999/018