An application of the method of additive chains to inversion in finite fields

What is it about?

We obtain estimates of complexity and depth of Boolean inverter circuits in normal and polynomial bases of finite fields. In particular, we show that it is possible to construct a Boolean inverter circuit in the normal basis of the field GF(2n) whose complexity is at most (λ(n − 1) + (1 + o(1))λ(n)/λ(λ(n)))M(n) and the depth is at most (λ(n − 1) + 2)D(n), where M(n), D(n) are the complexity and the depth, respectively, of the circuits for multiplication in this basis and λ(n) = ⌊log2 n⌋.

Featured Image