|
Вестник Московского университета. Серия 1: Математика. Механика, 2009, номер 4, страницы 3–7
(Mi vmumm882)
|
|
|
|
Эта публикация цитируется в 5 научных статьях (всего в 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$ раза (здесь и далее логарифмы двоичные, если явно не указано основание).
Ключевые слова:
булевы схемы, конечные поля, мультиплер, инвертор.
Поступила в редакцию: 24.12.2008
Образец цитирования:
С. Б. Гашков, И. С. Сергеев, “О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях $GF(2^n)$”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2009, № 4, 3–7
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm882 https://www.mathnet.ru/rus/vmumm/y2009/i4/p3
|
Статистика просмотров: |
Страница аннотации: | 134 | PDF полного текста: | 51 |
|