You are here: Home :: Area NEM :: Mathematics

S. B. Gashkov, I. S. Sergeev

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

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ⁿ) 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₂ n⌋.

Discrete Mathematics and Applications, Walter de Gruyter

Print ISSN: 0924-9266
Volume: 16, 12/2006
Pages: 601 - 618

Show full article (external site)

Show all available items of this journal

 

Area NEM