УДК 519.95
О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях GF(2n) / С.Б. Гашков, И.С. Сергеев // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. № 4. С. 3-7.
При n=(p-1)·pk, где p - такое простое число, что 2 - первообразный корень по модулю p и 2p-1-1 не кратно p2, для стандартного базиса в GF(2n) получены оценки сложности мультиплера O(log log p)nlog n log logpn и инвертора O(log p log log p)n log n log logpn. В частности, при p=3 получены оценка сложности умножения 5·5/8·n log3n log2log3n+O(nlog n) и оценка сложности инвертирования, которая больше указанной асимптотически в 2,5 раза (здесь и далее логарифмы двоичные, если явно не указано основание).
Ключевые слова: булевы схемы, конечные поля, мультиплер, инвертор.
Библиогр. 12.
