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. Seriya 1. Matematika. Mekhanika. 2009. № 4. P. 3-7 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 139-143].

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.

№ 4/2009