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.