Primality and identity testing via Chinese remaindering

Abstract

Gives a simple and new primality testing algorithm by reducing primality testing for a number n to testing if a specific univariate identity over Z_n holds. We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over Z_n for any n. The running time of the algorithms is polynomial in the size of the arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, e.g. the Schwartz-Zippel test (J.T. Schwartz, 1980; R.E. Zippel, 1979), the Chen-Kao (1997) test and the Lewin-Vadhan (1998) test. Our algorithms first transform the input polynomial to a univariate polynomial and then use Chinese remaindering over univariate polynomials to effectively test if it is zero.