<< Предыдущая

стр. 48
(из 48 стр.)

ОГЛАВЛЕНИЕ

Свойство 2. Каждый многочлен p(X) степени n, неприводимый над полем GF(2), является
n n
делителем двучлена X 2 ?1 + 1, и каждый делитель двучлена X 2 ?1 +1, неприводимый над полем
GF(2), имеет степень, равную n и менее.
Свойство 3. Все элементы поля GF(2n) можно получить как совокупность остатков от деления
n
?1
100...00 на неприводимый многочлен p(X), входящий в разложение двучлена ( X 2 +1). Эти остатки
n
– корни двучлена ( X 2 ?1 +1), т.е. обращают его в нуль. Число остатков равно (2n –1).
Свойство 4. В поле GF(2n) существует примитивный элемент ?, такой, что каждый ненулевой
элемент поля GF(2n) может быть представлен как некоторая степень ?, т.е. мультипликативная груп-
па GF(2n) является циклической.
4 4
Пример. Определение элементов ?i поля GF(2 ). Согласно cвойству 1 ненулевые элементы поля GF(2 ) являются
4
?1
корнями обобщенного двучлена ( X 2
15 15
+1)=(X +1). Двучлен (X +1) можно представить в виде произведения неприводимых
многочленов – сомножителей:
15 1 2 4 4 4
(X +1) = P(X ) ? P(X ) ? P1(X ) ? P2(X ) ? P3(X ),
где
1 2 2
P(X ) = (X +1), P(X ) = X + X +1,
4 4 4 4 3
P1(X ) = X + X +1, P2(X ) = X + X +1,
4 4 3 2
P3(X ) = X + X + X + X +1.
4
В соответствии со cвойством 3 вычислим элементы ?i поля GF(2 ) как совокупность остатков от деления 100...00 на
4 4
неприводимый многочлен P1(X )=X +X+1.
Процедура определения остатков
4 4 j
Делят на P1 (X ) = X + X +1 -10011 единицу с возраcтающим числом нулей, т.е. делят одночлены X , где j = 0, 1, 2,
4 0 1 2 3 4
3, …, на многочлен (X + X +1). Степени одночленов X , X , X , X меньше степени многочлена P1(X ) , поэтому первые четыре
4 0 1 2 3 4
остатка от деления на P1(X ) равны делимым, т.е. одночленам X , X , X , X . Для одночлена X - 10000 получаем остаток
10000 10011
10011
4
0011-X .
5
Для одночлена X - 100000 получаем остаток
100000 10011
10011
5
0110-X .
Схема вычисления остатков:
1000000000000000 10011
10011
4
X- 0011000
10011
7
X- 10110
10011
8
X- 010100
10011
10
X- 011100
10011
12
X- 11110
10011
13
X- 11010
10011
14
X- 10010
10011
15
X - 0001
0
(= X ).
4
Вычисленные остатки и нулевые элементы ?0–?14 поля Галуа GF(2 ) сведены в табл. П. 6.
Таблица П.6
i
?i
X Остаток
0
?0
X 0001
1
?1
X 0010
2
?2
X 0100
3
?3
X 1000
4
?4
X 0011
5
?5
X 0110
6
?6
X 1100
7
?7
X 1011
8
?8
X 0101
9
?9
X 1010
10
?10
X 0111
11
?11
X 1110
12
?12
X 1111
13
?13
X 1101
14
?14
X 1001
4
Поле Галуа GF(2 ) построено как поле многочленов с коэффициентами 0 и 1 по модулю неприводимого многочле-
на:
4 4
P(X ) = X + X +1 -1 0 0 1 1.

В поле Галуа GF(2n) определены четыре алгебраические операции. Операции сложения и вы-
читания выполняются как операции поразрядного сложения по модулю 2; операция умножения эле-
ментов поля выполняется как умножение соответствующих многочленов с приведением по модулю
неприводимого многочлена P(X), т.е. многочлена, по модулю которого построены элементы поля
GF(2n).
Пример. ?5 = 0110, ?6 =1100, ?5 + ?6 = 1010, так как
0110
1100
1 0 1 0.
Пример. ?14 =1001,
2 4
?14 ? ?14 = ? 14 = ?13 по mod P1(X ) - 1 0 0 1 1.
1001 1000001 10011
1001 10011
?13 -
1001 1 1 0 1.
1001
1 0 0 0 0 0 1.

Чтобы выполнить деление элемента b на элемент a в поле GF(2n) по модулю P(X), снача-
ла находят обратный элемент a–1 (mod P(X)), а затем вычисляют
b ? a–1 (mod P(X)).
Каждый двоичный вектор длиной n, исключая 0, является взаимно простым с неприводимым
многочленом P(X) независимо от значения P(X). Поэтому число вычетов, взаимно простых с P(X),
равно ?(P(X)) = 2n –1 (расширение функции Эйлера для многочленов). Поэтому
n
a–1 = a?(P(X)) –1 mod P(X) = a 2 ?2
mod P(X).
3
Пример. Пусть a =100 и P(X) =1011 в поле GF(2 ).
3
?2
a = 100 2
–1 6 2 4
(mod 1011) = 100 (mod 1011) = 100 ? 100 (mod 1011).
2
100 (mod 1011) = 10000 ? 10110 = 110
10000 1011
или 1011
110
4 2
100 (mod 1011) = 110 (mod 1011) = 010
110
?1 1 0 10100 1011
или 000 1011
110 010
100
10100
2 4
100 ? 100 (mod 1011) = 110 ? 010 (mod 1011) = 1100 (mod 1011) = 111
1100 1011
или 1011
111
–1
Итак, a = 111.
–1 –1
Проверка: a = 100, a = 111, P(X) = 1011, a ? a = 110 * 100 = 11100.




11100 1011
1011
1010
1011
001
–1
т.е. a ? a (mod 1011) =1.
Достоинства вычислений в поле GF(2n):
1. Все элементы поля Галуа имеют конечный размер, деление элементов не имеет каких-либо оши-
бок округления.
2. Сложение и вычитание элементов поля GF(2n) не требует деления на модуль.
3. Алгоритмы вычислений в поле GF(2n) допускают параллельную реализацию.
4. Для поля GF(2n) обычно применяют в качестве модуля трехчлен P(Xn) = Xn + X +1.
Длинная строка нулей между коэффициентами при Xn и X обеспечивает более простую реа-
лизацию быстрого умножения (с приведением по модулю). Трехчлен P(Xn) должен быть неприводи-
мым и примитивным.
Трехчлен P(Xn) = Xn + X +1 является примитивным для следующих значений n (n <1000):
1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63,
127, 153, 172, 303, 471, 532, 865, 900.

<< Предыдущая

стр. 48
(из 48 стр.)

ОГЛАВЛЕНИЕ