TR12-093 Authors: Charanjit Jutla, Vijay Kumar, Atri Rudra

Publication: 16th July 2012 17:37

Downloads: 4957

Keywords:

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.