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

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2006, номер 5, страницы 10–16 (Mi vmumm3821)

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

Математика

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

А. А. Бурцев, И. Б. Гашков, С. Б. Гашков


Аннотация: В работе доказывается, что для любого $\epsilon>0$ при любом $m,n=m^s$, и $s\ge s_\epsilon$ можно выбрать в поле $GF(2^n)$ базис, для которого схемная сложность умножения меньше $n^{1+\epsilon/2}$, а сложность инвертирования меньше $n^{1+\epsilon}$. При $n=2\cdot3^k$ для некоторого базиса получены для умножения оценки сложности $n(\log_3n)^{(\log_2\log_3n)/2+O(1)}$ и по порядку такие же оценки получены для инвертирования.
Библиогр. 12.

УДК: 519.7+512.624

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



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


© МИАН, 2024