RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2009, номер 4, страницы 3–7 (Mi vmumm882)

Эта публикация цитируется в 5 статьях

Математика

О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях $GF(2^n)$

С. Б. Гашковa, И. С. Сергеевb

a Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
b ФГУП НИИ "Квант", г. Москва

Аннотация: При $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$ раза (здесь и далее логарифмы двоичные, если явно не указано основание).

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

УДК: 519.95

Поступила в редакцию: 24.12.2008



Реферативные базы данных:


© МИАН, 2024