Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-093 | 1st July 2012 02:50

On the Circuit Complexity of Composite Galois Field Transformations


Authors: Charanjit Jutla, Vijay Kumar, Atri Rudra
Publication: 16th July 2012 17:37
Downloads: 4957


We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between representations of such fields which are nicely characterized. The exceptions show that the polynomials representing the fields must be of a regular form, which may be of independent interest. We characterize a family of transformations which can be implemented as cross-wires (permutations), without using any gates, which is very useful in designing hardware implementations -- and through bit-slicing, software implementations -- of computations based on Galois Field arithmetic. We also show that our lower bound is tight, by demonstrating a class of transformations which only require a linear number of gates.

ISSN 1433-8092 | Imprint