О применении метода аддитивных цепочек к инвертированию в конечных полях

Получены оценки сложности и глубины булевых схем для инвертирования в нормальных и полиномиальных базисах конечных полей. В частности, показано, что для инвертирования в нормальном базисе поля $\mathit{GF}(2^n)$ можно построить булеву схему со сложностью не более $(\lambda(n-1)+(1+o(1))\lambda(n)/\lambda(\lambda(n)))M(n)$ и глубиной не более $(\lambda(n-1)+2)D(n)$, где $M(n)$, $D(n)$ – соответственно сложность и глубина схемы для умножения в этом базисе, а $\lambda(n)=\lfloor\log_2n\rfloor$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 05–01–00994, программой Президента Российской Федерации поддержки ведущих научных школ, грант НШ 5400.2006.1, и программой фундаментальных исследований Отделения математических наук РАН “Алгебраические и комбинаторные методы математической кибернетики”, проект “Синтез и сложность управляющих систем”.