Charanjit S. Jutla, Vijay Kumar and Atri Rudra

On the Circuit Complexity of Isomorphic Galois Field Transformations
Abstract : A popular technique for efficient implementation of algorithms using finite fields is to do the computation in an isomorphic composite field. A key operation in this "method" is to transform the elements from the original field to the composite field. We study the circuit complexity of this operation and give a tight lower bound on the number of (constant fan-in exor) gates required. Along the way we characterize a certain class of irreducible polynomials.
Versions