Primality and identity testing via Chinese remaindering

Agrawal, M. ; Biswas, S. (1999) Primality and identity testing via Chinese remaindering Proceedings of IEEE 40th Annual Symposium on Foundations of Computer Science, 1999 . pp. 202-208. ISSN 0272-5428

Full text not available from this repository.

Official URL:

Related URL:


Gives a simple and new primality testing algorithm by reducing primality testing for a number n to testing if a specific univariate identity over Zn 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 Zn 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.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:95344
Deposited On:13 Nov 2012 11:56
Last Modified:13 Nov 2012 11:56

Repository Staff Only: item control page