Sixtors and Mod 6 Computations
Vince I. Grolmusz · Electronic colloquium on computational complexity · 2003
We consider the following phenomenon: with just one multiplication we can compute (3u+2v)(3x+2y) ≡ 3ux+4vy (mod 6), while computing the same polynomial modulo 5 needs 2 multiplications. We generalize this observation and we define some vectors, called sixtors, with remarkable zero-divisor properties. Using sixtors, we also generalize our earlier result (Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications, SIAM Journal on Computing, Vol. 32. No. 6.) for fast computation of wider classes of multi-variate polynomials, modulo composites.