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

Предложен метод реализации инвертирования в стандартных базисах конечных полей $GF(p^n)$ схемами над $GF(p)$ сложности $O(\varepsilon^{-1}n^{w+\varepsilon})$ и глубины $O(\varepsilon^{-1}\log n)$, где $\varepsilon>0$, а $w<1,667$ – экспонента умножения матриц размера $\sqrt n\times\sqrt n$ и $\sqrt n\times n$. Инвертирование в гауссовых нормальных базисах реализуется схемой сложности $O(\varepsilon^{-b}n^{1+c\varepsilon|\log\varepsilon|})$ и глубины $O(\varepsilon^{-1}\log n)$, где $b,c$ – некоторые константы.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 05–01–00994, программы президента Российской Федерации поддержки ведущих научных школ, проект НШ 5400.2006.1, и программы фундаментальных исследований Отделения математических наук РАН “Алгебраические и комбинаторные методы математической кибернетики”, проект “Синтез и сложность управляющих систем”.