О сложности и глубине булевых схем для умножения и инвертирования в конечных полях характеристики 2

Для сложности умножения в стандартном базисе поля $GF(2^n)$, где $n=2\cdot3^k$, получены оценка сложности умножения $5n\log_3n\log_2\log_3n+O(n\log n)$ и оценка сложности инвертирования, которая больше указанной асимптотически в $2,5$ раза. Как следствие, для сложности умножения двоичных многочленов степени $N$ справедлива верхняя оценка $(10+o(1))N\log_3N\log_2\log N$.
Указанные оценки обобщаются на случай других конечных полей. Для случая, когда $n=(p-1)p^k$, где $p$ – такое простое число, что $2$ есть первообразный корень по модулю $p$ и $2^{p-1}-1$ не кратно $p^2$, для стандартного базиса в поле $GF(2^n)$ построены мультиплер сложности $(C+o(1))(n\log_3n\log_2\log n)$ и инвертор сложности $O(\log p)n\log n\log\log n$, где $C\le10$.
Работа выполнена при поддержке РФФИ, проекты 11–01–00508 и 11–01–00792-а, и программы фундаментальных исследований Отделения математических наук РАН “Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения”, проект “Задачи оптимального синтеза управляющих систем”.