The complexity and depth of Boolean circuits for multiplication and inversion in some fields GF(2 n )
Sergey Borisovich Gashkov, Igor' Sergeevich Sergeev · Moscow University Mathematics Bulletin · 2009
Let n = (p − 1) · p k , where p is a prime number such that 2 is a primitive root modulo p, and 2 p−1 − 1 is not a multiple of p 2. For a standard basis of the field GF(2 n ), a multiplier of complexity O(log log p)n log n log log p n and an inverter of complexity O(log p log log p)n log n log log p n are constructed. In particular, in the case p = 3 the upper bound $$ 5\frac{5} {8}n\log _3 n\log _2 \log _3 n + O(n\log n) $$ for the multiplication complexity and an upper bound for the inversion complexity which is asymptotically 2.5-times greater are obtained (hereafter, if not indicated explicitly, all logarithms are base two).