On Modular Counting with Polynomials
Kristoffer Arnsfelt Hansen · 2006
For any integers m and l, where m has r sufficiently large (depending on l) factors, that are powers of r distinct primes, we give a construction of a (symmetric) polynomial over Z/sub m/ of degree O(/sup r//spl radic/n) that is a generalized representation (commonly also called weak representation) of the MOD/sub l/ function. We give a detailed study of the case when m has exactly two distinct prime factors, and classify the minimum possible degree for a symmetric representing polynomial.