An application of the method of additive chains to inversion in finite fields
Sergey Borisovich Gashkov, Igor' Sergeevich Sergeev · Discrete Mathematics and Applications · 2006
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 (2 n ) 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 ) = ⌊log 2 n ⌋.