ECCC-Report TR12-093https://eccc.weizmann.ac.il/report/2012/093Comments and Revisions published for TR12-093en-usMon, 16 Jul 2012 17:37:28 +0300
Paper TR12-093
| On the Circuit Complexity of Composite Galois Field Transformations |
Charanjit Jutla,
Vijay Kumar,
Atri Rudra
https://eccc.weizmann.ac.il/report/2012/093We 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.Mon, 16 Jul 2012 17:37:28 +0300https://eccc.weizmann.ac.il/report/2012/093