УДК 519.95

О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях GF(2^n) / С. Б. Гашков, И. С. Сергеев. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. № 4. С. 3-7.

При n = (p-1)\cdot p^k, где p — такое простое число, что 2 — первообразный корень по модулю p и 2^{p-1}-1 не кратно p^2, для стандартного базиса в GF(2^n) получены оценки сложности мультиплера O(\log \log p)n\log n \log\log_p n и инвертора O(\log p\log\log p)n\log n \log\log_p n. В частности, при p=3 получены оценка сложности умножения

\displaystyle 5\frac{5}{8}n\log_3 n \log_2\log_3 n + O(n\log n) и оценка сложности инвертирования, которая больше указанной асимптотически в 2,5 раза (здесь и далее логарифмы двоичные, если явно не указано основание).

Ключевые слова: булевы схемы, конечные поля, мультиплер, инвертор.

Библиогр. 12.