On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2

摘要

For the complexity of multiplication in a standard basis of the field GF(2~n), where n D=2·3~k, the upper bound 5n log_3 n log_2 log_3 n + O(n log n) for multiplication complexity and an asymptotically 2.5 times greater bound for inversion complexity are obtained. As a consequence, for the complexity of multiplication of binary polynomials the upper bound (10 + o(1))N log_3 N log_2 logN is valid.