Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-074 | 24th June 2003 00:00

Sixtors and Mod 6 Computations

RSS-Feed




TR03-074
Authors: Vince Grolmusz
Publication: 9th October 2003 17:41
Downloads: 1169
Keywords: 


Abstract:

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,
ECCC Report TR02-052) for fast computation of much wider classes of
multi-variate polynomials, modulo composites.



ISSN 1433-8092 | Imprint