RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2009 Number 4, Pages 3–7 (Mi vmumm882)

This article is cited in 5 papers

Mathematics

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

S. B. Gashkova, I. S. Sergeevb

a Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Research Institute "Kvant", Moscow

Abstract: 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.

Key words: Boolean schemes, finite fields, multiplier, invertor.

UDC: 519.95

Received: 24.12.2008



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025