The complexity and depth of Boolean circuits for multiplication and inversion in some fields $GF(2^n)$

S. B. Gashkov   ; I. S. Sergeev

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 4 (2009), pp. 3-7

Résumé

Let $n=(p-1)\cdot p^k,$ where $p$ is a prime number such that $2$ is a primitive root modulo $p$, $2^{p-1}-1$ is not divided by $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 invertor 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 the asymptotically $2,5$ times greater bound for the inversion complexity are obtained.