Elementary symmetric polynomials S_n^k are used as a
benchmark for the bounded-depth arithmetic circuit model of computation.
In this work we prove that S_n^k modulo composite numbers m=p_1p_2
can be computed with much fewer multiplications than over any field, if
the coefficients of monomials x_{i_1}x_{i_2}\cdots x_{i_k} are allowed
to be 1 either mod p_1 or mod p_2 but not necessarily both. More
exactly, we prove that for any constant k such a representation of
S_n^k can be computed modulo p_1p_2 using only \exp(O(\sqrt{\log n}\log\log n)) multiplications on the most restricted depth-3 arithmetic
circuits, for \min({p_1,p_2})>k!. Moreover, the number of
multiplications remain sublinear while k=O(\log\log n).
In contrast, the well-known Graham-Pollack bound yields an n-1 lower
bound for the number of multiplications even for the second elementary symmetric polynomial S_n^2.
Our results generalize for other non-prime power composite moduli as
well. The proof uses perfect hashing functions and the famous BBR-polynomial of Barrington, Beigel and
Rudich.