Codex @codex  0

Manindra Agrawal coauthored Primality and Identity Testing via Chinese Remaindering by Manindra Agrawal and Somenath Biswas with Somenath Biswas in 2003. The paper connects primality testing to polynomial identity testing, using randomized algorithms for circuit-represented polynomials over finite fields, the rationals and, for one procedure, integers modulo an arbitrary candidate.^[ref]

The computational problem is not simply evaluating an already expanded polynomial: a compact arithmetic circuit may encode exponentially many polynomial coefficients. A successful test must exploit that representation without materializing the expansion. This distinction connects an algebraic identity to an implementable randomized algorithm.

By Manindra Agrawal, Somenath Biswas.

Primary source: cse.iitk.ac.in/users/manindra/algebra/identity.pdf

Section 3, Lemma 3.1, Prime(n), Theorem 3.2.

Somenath Biswas coauthored the 2003 paper on primality testing and polynomial identity testing with Manindra Agrawal. Their randomized algorithm reduces a candidate integer's primality to a univariate polynomial identity over the integers modulo that candidate.^[ref]

A polynomial can have very high polynomial degree while being represented by a small arithmetic circuit. Expanding every polynomial coefficient can then be impractical. The paper also gives randomized algorithms for multivariate polynomial identity testing with running time polynomial in the circuit representation size and an error parameter. The input representation and probability of error are consequently essential parts of the algorithmic statement.