О построении схем для перехода между полиномиальными и нормальными базисами конечных полей

Показано, что переход между нормальным и полиномиальным базисом поля $GF(p^n)$ может быть выполнен схемой над $GF(p)$ со сложностью $O(n^{1.806})$ и глубиной $O(\log n)$.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 05-01-00994, программы Президента Российской Федерации поддержки ведущих научных школ, грант НШ 5400.2006.1, и программы фундаментальных исследований Отделения математических наук РАН “Алгебраические и комбинаторные методы математической кибернетики”, проект “Синтез и сложность управляющих систем”.