Реализация логическими схемами операций умножения и инвертирования в конечных полях характеристики два

• Автор: Хохлов, Роман Анатольевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 157 с.

1 Введение

2 Известные методы умножения в конечных полях характеристики два

3 Известные методы инвертирования в конечных полях характеристики два

4 Общие методы

4.1 Сведение инвертирования В поле размерности П = ПП2 к инвертированию в поле размерности п2

4.2 Сведение инвертирования в поле размерности п — ПіПгИз

к инвертированию в поле размерности п3

4.3 Расширение второй степени

4.4 Расширение третьей степени

4.5 Расширение четвертой степени

4.6 Расширение пятой степени

4.7 Расширение шестой степени
5 Примеры
5.1 вР{ 22)
5.1.1 Оптимальный нормальный базис 2-го типа, х2 + х + 1
5.2 С7РХ23)
5.2.1 Оптимальный нормальный базис 3-го типа, х3 + х2 +1
5.3 (Щ26) = С^(223)
5.3.1 Оптимальный нормальный базис 3-го типа, х3 + х1 +1
5.4 йР{ 210) = 22")
5.4.1 Оптимальный нормальный базис 2-го типа, хъ+х4+
х2 + х +
5.5 СРХ2в) = СР(2*)
5.5.1 Оптимальный нормальный базис 2-го типа, х2 + х + 1
5.6 СРХ212) = СР,(23")
5.6.1 Оптимальный нормальный базис 1-го типа, х4 -г Xі +
х2 + х +
5.7 СРХ215) = СРХ 235)
5.7.1 Оптимальный нормальный базис 2-го типа, х5+х4+
х2 + х + 1 г
5.8 СРХ2ЗП) = сщг235) и вр(230) = с?РХ2325)

5.8.1 Оптимальный нормальный базис 2-го типа, ж5 +х4 +
X2 + X +
5.9 ОГ(230) = Сі^(2253)
5.9.1 Оптимальный нормальный базис 3-го типа, х3 + х2 +1
5.10 GF(2ЗQ) = GF(2з52)
5.10.1 Оптимальный нормальный базис 2-го типа, х2 + х + 1
5.11 СР{ 24)
5.11.1 Оптимальный нормальный базис 1-го типа, х4+х3 +
х2 + х +
5.11.2 Стандартный базис, ж4 + х +
5.12 GF(212) = 243)
5.12.1 Оптимальный нормальный базис 3-го типа, л3 + х2 +1
5.13 GF(220) = GF(245)
5.13.1 Оптимальный нормальный базис 2-го типа, х5+х4 +
х2 + х +
5.14 GF(25)
5.14.1 Оптимальный нормальный базис 2-го типа, х5+х4 +
х2 + х + I
5.14.2 Стандартный базис, х5 + х2 +
5.15 СГ(210) = GF(252)
5.15.1 Оптимальный нормальный базис 2-го типа, х2 + х + 1
5.16 С^(215) = С^(253)
5.16.1 Оптимальный нормальный базис 3-го типа, х3 + х2 +1
5.17 GF(220) = СР{25і)
5.17.1 Оптимальный нормальный базис 1-го типа, х4+х3 +
х2 + х +
5.18 СР(2в)
5.18.1 Оптимальный нормальный базис 2-го типа, х6+х5 +
ж4 + х +
5.18.2 Стандартный базис, х6 + х3 +
5.19 GF(230) = GF(265)
5.19.1 Оптимальный нормальный базис 2-го типа, х5+х4+
х2 + х +
5.20 Заключение
6 Общие методы. Продолжение
6.1 Расширение второй степени полей с четной степенью
7 Примеры
7.1 GF(24) = GF(222)
7.1.1 Стандартный базис {1, а}

7.2 (3^(24) = 22")
7.2.1 Нестандартный базис {а, /3}
7.3 б^(28) = £Т(242)
7.3.1 Нестандартный базис {а,/?}
7.3.2 Стандартный базис {1,а}
7.3.3 "Башня"базисов в поле С1Р(28)
7.4 (3^(216)
7.4.1 "Вашня"базисов в поле ОУ<’(216) = СР(242 )
7.4.2 "Башня"базисов в поле 216)
7.5 СР{2и) = СР{2^)
7.5.1 Оптимальный нормальный базис 3-го типа, ж3 + х2 +1117
7.6 СЯ224) = СР(243")
7.6.1 Башня базисов. Нестандартный базис {а,/3}
7.7 вР(248) = С?^(2422 )
7.7.1 Оптимальный нормальный базис 3-го тина, х3 + х2 +1122
7.8 ОР(2120) = ОР(24235 )
7.8.1 Оптимальный нормальный базис 2-го типа, ж5+.т4+
х2 + х + 1
8 Общие методы. ,'Башни"расширений
8.1 Инвертирование в башнях полей и схемы ^^„^2(7x3)
8.2 О схемах для М{п, щщ)
8.3 Биквадратное расширение полей
8.3.1 Умножение
8.3.2 Инвертирование
8.4 Расширение шестой степени
8.4.1 Умножение
8.4.2 Инвертирование
9 Примеры
9.1 <УР(212) = вР(23*)
9.1.1 Биквадратное расширение
9.2 СР(220) = 25')
9.2.1 Биквадратное расширение
9.3 СР{230) = С.Р(256)
9.3.1 Расширение шестой степени
10 Сравнения с известными результатами
10.1 Таблица
10.2 Метод аддитивных цепочек

Таким образом мы вычислили матрицу Т,
/ 0 1 0 0 0 0
і 0 0 0 1 0
0 0 0 1 1 0
0 0 1 0 0 1
0 1 1 0 0 0
V 0 0 0 1 0 1
которая определяется равенством о»2"' = a2m+1 = ^2 a2 tmk, где m

0,1, 2, 3,4, 5. Напомним, что "матрицей умножспия"в нормальном базисе называется матрица А ),4—0,1,.., —i> ^(j~j mod n),(—j mod n)-
А то есть "матрица умножения для данного нормального базиса равна
/010000
1 0 0 0 1
0 0 0 1 1
0 0 1 0 0
0 110 0 0 0 0 0 1 0 1
Как видно сложность этой матрицы равна 11 = 2-6 — 1, поэтому выбранный базис является оптимальным нормальным, то есть нормальным базисом с наименьшей сложностью умножения.
Теорема 4.11. В расширении шестой степени GF((2П)6) поля GF(2n), где п взаимно просто с 6, при выборе нормального базиса имеют место следующие рекуррентные соотношения для сложности и глубины умножения
Ь(М(6п)) < 21 L(M(n)) + 60п,
D(M(6n)) < D(M(n)) +4.
Доказательство. Не теряя общности, проведем доказательство для конкретного нормального базиса, а именно для базиса с многочленом ха+х5+х4+х+1. Правда, если взять другой многочлен, то построенная в доказательстве схема будет отличаться, но оценки останутся прежними. Явно выпишем произведение двух элементов
ху = {х^а + ада2 + х2аА + хза& + ада16 + х$а32)х
х {Уоа + а2 + у2аА + Уза6 + у^а16 + у5а32)