Ashish Sabharwal

Primality and Identity Testing via Chinese Remaindering

I will present a FOCS 1999 paper by Agrawal and Biswas that gives a randomized primality testing algorithm using the same characteristic property of prime numbers as used by the new deterministic poly-time algorithm, namely, n is prime iff (1+z)^n - 1 - z^n is identically 0 modulo n. Although this approach is less efficient than those that appeared earlier (e.g. Miller-Rabin, Solovay-Strassen), the algorithm as well as its analysis are substantially simpler. The paper reduces the primality problem to polynomial identity testing and presents a randomized solution for the latter using Chinese remaindering.