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

S. B. Gashkov ; I. S. Sergeev

Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 56-72

Résumé

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 $\mathit{GF}(2^n)$ whose complexity is at most $(\lambda(n-1)+(1+o(1))\lambda(n)/\lambda(\lambda(n)))M(n)$ and the depth is at most $(\lambda(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 $\lambda(n)=\lfloor\log_2n\rfloor$.