Файл: Кодирования.pdf

возможности воспользоваться таблицами, то можно проверить, является ли многочлен неприводимым и примитивным путем построения поля, которое в ином случае построено быть не может. Также возможность построения поля можно оценить, попытавшись определить значение полинома x p
m
−1
mod p(x).
Так как поле Галуа является циклическим, то, в случае, если поле может быть построено, остаток от деления x p
m
−1
на p(x) должен быть равен единице.
В табл.
7.1
приведены примеры образующих полиномов p(x) для неко- торых степеней поля GF(2
m
).
Таблица 7.1
Примеры образующих полиномов p(x) поля GF(2
m
)
Степень
Полином
Степень
Полином
1
x
+ 1 2
x
2
+ x + 1 3
x
3
+ x + 1 4
x
4
+ x + 1
x
3
+ x
2
+ 1
x
4
+ x
3
+ 1 5
x
5
+ x
2
+ 1 6
x
6
+ x + 1
x
5
+ x
3
+ 1
x
6
+ x
4
+ x
3
+ x + 1
x
5
+ x
3
+ x
2
+ x + 1
x
6
+ x
5
+ 1
x
5
+ x
4
+ x
2
+ x + 1
x
6
+ x
5
+ x
2
+ x + 1
x
5
+ x
4
+ x
3
+ x + 1
x
6
+ x
5
+ x
3
+ x
2
+ 1
x
5
+ x
4
+ x
3
+ x
2
+ 1
x
6
+ x
5
+ x
4
+ x + 1 7.1.2. Левый степенной базис и представление элементов поля
На практике элементы поля Галуа представляются в трех видах.
1. Степень первого элемента поля.
2. «Двоичное» (полиномиальное) представление элемента поля через левый степенной базис.
3. Десятичное представление элемента поля.
4. Представление элемента поля через двойственный базис.
Первый элемент поля Галуа будем обозначать как ε, тогда остальные элементы поля будут рассматриваться как его степени.
ε , ε
2
, ε
3
, . . . , ε
p m
−1
Так как поле Галуа является циклическим, ε
p m
= ε.
Одним из свойств расширенного поля Галуа GF(p m
) является то, что любой элемент поля может быть выражен суммой из m элементов поля. Как правило, для выражения элементов используются первые m элементов
[1, ε, ε
2
, . . . , ε
m
−1
],
(7.2)
получившие название левый степенной базис (ЛСБ). В различных источниках применяются также термины полиномиальный базис и стандартный базис.
43

Полиномиальное представление элемента поля через левый степенной базис выражается по формуле a
0
+ a
1
ε + a
2
ε
2
+ . . . + a m
−1
ε
m
−1
,
где коэффициенты a i
принадлежат простому полю GF(p).
По аналогии с полиномом, это выражение может быть представлено в виде вектор-строки коэффициентов
[a
0
, a
1
, a
2
, . . . , a m
−1
].
Соответственно, элемент поля представляется также и в виде многочлена f
(x) = a
0
+ a
1
x
+ a
2
x
2
+ . . . + a m
−1
x m
−1
(7.3)
В случае рассматриваемых нами двоичных полей, каждый из коэффициен- тов a i
может быть равен 0 или 1. И вектор-строка может быть записана как двоичное число («двоичный» полином), которое может быть преобразовано в десятичное по стандартному правилу преобразования двоичного числа в де- сятичное (пп.
2.2.1
).
Следует отметить, что в математических системах Matlab/Octave для двоичных чисел по умолчанию используется обратная запись, от младшей сте- пени к старшей (слева-направо). Соответственно, преобразование в десятич- ный вид и обратно будет иным.
Для примера приведем поле Галуа GF(2 3
), построенное на основе поли- нома p(x) = x
3
+ x + 1 (табл.
7.2
).
Таблица 7.2
Поле Галуа GF(2 3
). p(x) = x
3
+ x + 1.
Элемент
Полином
Двоичный вид
Десятичный вид
Десятичный вид поля a
0
+ a
1
x
+ a
2
x
2
{a
0
a
1
a
2
}
обычный
(Matlab/Octave)
ε
0
= 1 1
100 4
1
ε
x
010 2
2
ε
2
x
2 001 1
4
ε
3 1 + x
110 6
3
ε
4
x
+ x
2 011 3
6
ε
5 1 + x + x
2 111 7
7
ε
6 1 + x
2 101 5
5 7.1.3. Пример построения поля Галуа
Для примера рассмотрим процесс построения поля Галуа GF(2 3
) c об- разующим полиномом p(x) = x
3
+ x + 1, показанного в табл.
7.2 44

Каждый элемент поля ε
i можно представить в виде соответствующего ему полинома x i
mod p(x). То есть, каждому элементу поля ε
i соответствует полином, равный остатку от деления x i
на p(x).
Первые элементы поля ε
0
= 1, ε, ε
2
образуют левый степенной базис поля. Им соответствуют двоичные полиномы с тем же значением показателя степени.
Для определения оставшихся элементов поля просто делим соответ- ствующие им полиномы на p(x) и берем остаток от деления. Например,
x
3
x
3
+ x + 1
= 1 +
x
+ 1
x
3
+ x + 1
⇒
ε
3
= 1 + x.
Заметим, что элемент поля, следующий за левым степенным базисом, равен образующему полиному поля за вычетом одночлена старшей степени x m
, ко- торый для рассматриваемого примера равен x
3
Также, для определения элементов поля можно использовать и другой способ. Зная элемент ε
3
, дальнейшие элементы поля получаем путем умноже- ния элемента предыдущей степени на элемент ε и приведением получившего- ся результата к левому степенному базису. По другому этот процесс можно описать как побитовый сдвиг значения элемента поля влево (вправо, если го- ворить о форме представления в Octave) со сложением по модулю 2 с ε
3
при переносе единицы за границу элемента поля:
ε
4
= ε
3
· ε = (1 + x) · x = x + x
2
= 110 2
;
ε
5
= ε
4
· ε = (x + x
2
) · x = x
2
+ x
3
= (1 + x) + x
2
= 1 + x + x
2
= 111 2
;
ε
6
= ε
5
· ε = (1 + x + x
2
) · x = x + x
2
+ x
3
= x + x
2
+ 1 + x = 1 + x
2
= 101 2
;
ε
7
= ε
6
· ε = (1 + x
2
) · x = x + x
3
= x + 1 + x = 1 = ε
0
= 001 2
Можно видеть, что поле циклично. Элемент поля ε
7
равен элементу поля ε
0 7.1.4. Характеристическая матрица
Каждому элементу поля ε
k взаимнооднозначно соответствует много- член:
F
k
= a
0
E + a
1
F + a
2
F
2
+ . . . + a m
−1
F
m
−1
,
(7.4)
где F — характеристическая матрица, а E = F
0
— единичная матрица.
Характеристическая матрица F для образующего полинома p(x) = x
3
+
x
+ 1 равна
F =


ε
ε
2
ε
3


=


010 100 011


45

Матрицу F
i для поля GF(2
m
) можно представить в общем виде:
F
i
=




ε
i
ε
i
+1
ε
i
+m−1




(7.5)
Для рассмотренного выше в табл.
7.2
поля матрица F
3
равна
F
3
=


ε
3
ε
4
ε
5


=


011 110 111


7.1.5. Двойственный базис поля
В работах [
20
] и [
21
] показано, что для любого степенного базиса (γ
1
,
γ
2
, . . . , γ
m
) поля Галуа GF(p m
) существует двойственный ему базис (ω
1
, ω
2
,
. . . , ω
m
), который также позволяет выразить все элементы поля Галуа.
В [
20
] доказано, что базис (ω
1
, ω
2
, . . . , ω
m
) двойственный степенному базису (γ
1
, γ
2
, . . . , γ
m
), равному (ε
n
, ε
n
+1
, . . . , ε
n
+m−1
), рассчитывается по формуле:
ω
i
= ε
−n
α
i
;
i
= 1, 2, . . . , m,
(7.6)
где коэффициенты α
i равны [
20
]:
α
i
=
m
− j
∑
l
=0
p m
− j−l
ε
l i
p
0
(ε
i
)
;
GF(2
m
),
(7.7)
где p j
— коэффициенты характеристического многочлена p(x).
При использовании левого степенного базиса (1, ε, . . . , ε
m
−1
), элементы
ω
i двойственного ему базиса совпадают с коэффициентами α
i
В некоторых работах, например [
21
] и [
22
], двойственный базис называ- ют дополняющим или взаимным базисом.
7.1.6. Свойства полей Галуа
1. Все отличные от нуля элементы поля GF(p m
) образуют мультипли- кативную группу порядка p m
− 1. Тогда для любого элемента поля ε имеет место равенство
ε
p m
−1
= 1.
(7.8)
2. В поле GF(p m
) всегда существует первообразный элемент ε, т. е. эле- мент порядка p m
− 1. Каждый ненулевой элемент поля может быть представ- лен как некоторая степень одного и того же первообразного элемента ε. Ины- ми словами: мультипликативная группа поля Галуа циклична.
46

3. Любой элемент поля GF(p m
) можно представить в виде a
0
+ a
1
ε + a
2
ε
2
+ . . . + a m
−1
ε
m
−1
(7.9)
4. В поле GF(p m
) имеет место равенство
(a + b)
p
= a p
+ b p
(mod p).
(7.10)
5. Если элемент ε поля GF(p m
) есть корень неприводимого по модулю p
многочлена P(x) степени m, то остальными корнями P(x) будут элементы
ε
p
, ε
p
2
, . . . , ε
p m
−1 6. Для любого простого числа p и любого примитивного многочлена
P
(x) степени m, т. е. минимального многочлена примитивного элемента поля
GF(p m
) [
19
], существует только одно поле Галуа GF(p m
), иными словами, по- ля Галуа GF(p m
), образованные различными неприводимыми примитивными многочленами степени m, изоморфны.
7.2. Основные действия над элементами поля
7.2.1. Логарифмирование и антилогарифмирование
Как было показано в пп.
7.1.2
, любой элемент поля ε
i может быть пред- ставлен двоичным вектором или многочленом вида (
7.3
).
Возьмем логарифм по основанию ε от элемента поля, представленного в виде ε
i
. Получим равенство:
log
ε
ε
i
= i.
(7.11)
Операция, реализованная по такому правилу, называется логарифми- рованием. Для целочисленных значений i данный вид логарифма принято на- зывать дискретным.
Смысл операции (
7.11
) состоит в поиске показателя степени i при ε
i
, т. е.
для некоторого элемента поля, заданного в виде вектора. Показатель степени может принимать значения i = 0, 1, 2, . . . , 2
m
− 2, где 2
m
— порядок поля.
При выполнении операции логарифмирования, необходимо учитывать одну особенность. В любом поле Галуа присутствует нулевой элемент, лога- рифм которого не определен. Следовательно, устройство или алгоритм, ре- ализующие эту операцию должны обрабатывать это исключение. Например,
при программной реализации, учитывая, что степени любых элементов поля можно свести к диапазону 0, 1, . . . , 2
m
− 2, для логарифма нуля можно ис- пользовать условное обозначение «−1».
Операция, противоположная операции (
7.11
), называется антилогариф- мированием. В этом случае необходимо найти вектор при известном показа- теле степени элемента. То есть при заданном i элемента поля ε
i определяется соответствующий ему вектор.
47

Для примера возьмем элемент ε
4
= 011 поля GF(2 3
), представленно- го в табл.
7.2
. Из формулы (
7.11
) следует, что логарифм ε
4
равен log
ε
011 =
log
ε
ε
4
= 4, а антилогарифм 4 равен antilog
ε
4 = ε
4
= 011.
Логарифм и антилогарифм применяются для проведения базовых опе- раций над элементами поля.
Различные варианты реализации операций логарифмирования и антило- гарифмирования рассмотрены в [
20
].
На практике при написании программ применяют два основных способа логарифмирования/антилогарифмирования. Первый способ — табличный. В
этом случае заранее создаются две таблицы. В одной содержится зависимость значения элемента от его степени, в другой — зависимость степени элемен- та от его значения. Операции реализуются простой выборкой по индексу из соответствующей таблицы. Для больших полей способ требует большого объ- ема памяти. Второй способ заключается в последовательной генерации эле- ментов поля до получения необходимого значения. Для больших полей требу- ются значительные временные затраты. Сотрудником СПбГУТ Дмитрием Ку- куниным был предложен способ логарифмирования, сочетающий в себе эти два метода. При этом создается таблица с контрольными точками и произво- дится динамическая генерация элементов до получения необходимого. Этот способ является оптимальным для больших полей как по быстродействию,
так и по требуемой для хранения таблиц памяти [
23
].
7.2.2. Сложение элементов поля
Для того, чтобы произвести сложение элементов поля ε
i и ε
j
, необхо- димо выразить эти элементы через левый степенной базис:
ε
i
= a
0
+ a
1
ε + a
2
ε
2
+ . . . + a m
−1
ε
m
−1
⇔ {a
0
a
1
a
2
. . . a m
−1
};
ε
j
= b
0
+ b
1
ε + b
2
ε
2
+ . . . + b m
−1
ε
m
−1
⇔ {b
0
b
1
b
2
. . . b m
−1
}.
(7.12)
Результатом сложения элементов (
7.12
) будет элемент
ε
k
= ε
i
+ ε
j
= c
0
+ c
1
ε + c
2
ε
2
+ . . . + c m
−1
ε
m
−1
⇔ {c
0
c
1
c
2
. . . c m
−1
},
(7.13)
где c i
= a i
+ b i
(mod p).
Схема устройства, реализующего сложение элементов, представленных в виде вектора, состоит из сумматора, поэлементно складывающего эти век- торы по mod 2.
Сложение элементов (
7.12
), в случае, когда они представлены их сте- пенями i и j, требует преобразований и, соответственно, наличия в схеме блоков, производящих операции логарифмирования и антилогарифмирова- ния (рис.
7.1
) [
20
].
48

antilog antilog
⊕
log j
i
{a
0
a
1
. . . a m
−1
}
{b
0
b
1
. . . b m
−1
}
{c
0
c
1
. . . c m
−1
}
k
Рис. 7.1. Схема сложения элементов поля, представленных индексами (степенями)
Нужно отметить, что в том случае, когда складываемые элементы рав- ны, т. е. имеют одинаковую по модулю (p m
− 1) степень, их сумма будет равна нулю. В этом случае, как было отмечено в пп.
7.2.1
, блок логарифмирования
(рис.
7.1
) должен обработать это исключение и передать на выход особый сиг- нал, соответствующий нулевому элементу.
7.2.3. Перемножение элементов поля
Умножение элементов поля (
7.12
), выраженных через левый степенной базис, производится с учётом выражений (
7.9
) и (
7.4
):
ε
k
= ε
i
· ε
j
= {a
0
a
1
. . . a m
−1
} · F
j
=
= {a
0
a
1
. . . a m
−1
} · (b
0
E
+ b
1
F
+ ... + b m
−1
F
m
−1
) =
= b
0
({a
0
a
1
. . . a m
−1
}E) + . . . + b m
−1
({a
0
a
1
. . . a m
−1
}F
m
−1
) =
= {c
0
c
1
. . . c m
−1
}.
(7.14)
На рис.
7.2
показана схема, реализующая умножение двух элементов по- ля GF(2
m
), согласно формуле (
7.14
) [
20
].
×E
×F
· · ·
×F
m
−1
×
×
×
ε
i
= {a
0
a
1
. . . a m
−1
}
b
0
b
1
b m
−1
c
0
c
1
c m
−1
ε
j
ε
k
Рис. 7.2. Структурная схема прямого умножителя элементов в поле GF(2
m
)
В случае, когда элементы поля (
7.12
) выражены их показателями сте- пени i и j, их произведение определяется путём сложения этих показателей степеней элементов:
ε
k
= ε
i
· ε
j
= ε
i
+ j
,
(7.15)
49

где i + j приводится по mod (2
m
− 1).
Для того, чтобы произвести умножение элементов поля, выраженных через левый степенной базис, согласно формуле (
7.15
), необходимо сначала произвести логарифмирование элементов поля (
7.12
), затем сложить показа- тели степеней и результат перевести в вектор с помощью операции антилога- рифмирования. На рис.
7.3
изображена структурная схема логарифмического умножителя элементов, реализующего данный принцип [
20
].
log log
∑
antilog
ε
j
ε
i i
j k
= (i + j)mod (2
m
− 1)
ε
k
Рис. 7.3. Структурная схема умножения элементов поля через операции логарифмирования и антилогарифмирования
Необходимо учесть, что в том случае, когда один из множителей равен нулю, результат также равен нулю, а проведение операций логарифмирова- ния невозможно. Следовательно, устройство или программный алгоритм, ре- ализующие схему умножения, приведенную на рис.
7.3
, должны обрабатывать этот вариант.
7.2.4. Возведение элемента поля в степень
Возведение элемента поля ε
i в степень j осуществляется по формуле:
(ε
i
)
j
= ε
i
· j
,
(7.16)
где произведение i · j приводится по модулю 2
m
− 1.
Схема реализации операции возведения в степень с использованием опе- раций логарифмирования и антилогарифмирования приведена на рис.
7.4
[
20
].
log
∏
antilog
ε
i j
i k
= (i · j) mod (2
m
− 1)
ε
k
Рис. 7.4. Структурная схема возведения элемента поля в степень
Так же, как и в случае логарифмического умножителя, устройство или программный алгоритм, реализующие логарифмическую схему операции воз- ведения в степень, должны учитывать случай, когда элемент поля ε
i будет равен нулю. Результат при этом также будет равен нулю.
50

Отдельного внимания заслуживает операция возведения в квадрат. Воз- ведение элемента поля ε
i
, представление которого через левый степенной ба- зис показано в (
7.12
), в квадрат можно представить в соответствии с (
7.10
) как
[
20
]:
(ε
i
)
2
= (a
0
+ a
1
ε + a
2
ε
2
+ . . . + a m
−1
ε
m
−1
)
2
=
= a
0
+ a
1
ε
2
+ a
2
(ε
2
)
2
+ . . . + a m
−1
(ε
m
−1
)
2
(7.17)
Соответственно, формулу (
7.17
) можно представить в векторном виде как
{a
0
a
1
a
2
. . . a m
−1
}X
2
= {c
0
c
1
c
2
. . . c m
−1
},
(7.18)
где X
2
— матрица порядка m равная
X
2
=







ε
0
ε
2
ε
4
ε
2(m−1)







Аналогично реализуются операции возведения в четвёртую, восьмую и более высокие степени, показатель которых равен степени двойки [
20
]. Соот- ветствующие матрицы равны
X
4
=







ε
0
ε
4
ε
8
ε
4(m−1)







,
X
8
=







ε
0
ε
8
ε
16
ε
8(m−1)







7.2.5. Обращение элемента поля
Как показано в п.
7.1
, поле Галуа представляет собой конечное множе- ство, состоящее из элементов, обладающих свойствами поля, а это значит, что каждому элементу поля ε
i соответствует обратный ему элемент ε
−i
Как показано в пп.
7.1.6
ненулевые элементы конечного поля GF(2
m
)
образуют циклическую мультипликативную группу порядка 2
m
− 1, следова- тельно для любого ненулевого элемента ε
i
, согласно малой теореме Ферма
[
24
], справедливо равенство:
(ε
i
)
2
m
−1
= 1.
(7.19)
Как следует из (
7.19
), для нахождения ε
−i нужно элемент ε
i возвести в степень 2
m
− 2:
(ε
i
)
2
m
−2
= ε
−i
(7.20)
51

7.2.6. Деление элементов поля
Операция деления элементов поля (
7.12
) может быть представлена сле- дующим образом:
ε
k
=
ε
i
ε
j
= ε
i
· ε
− j
,
(7.21)
где ε
− j
— элемент поля, обратный элементу ε
j
Таким образом, операция деления элементов поля может быть реали- зована через операцию умножения с обращением делителя. На рис.
7.5
пред- ставлена схема, реализующая данный принцип.
log log
Обращение
∑
antilog
ε
j
ε
i i
j
− j k
= (i + (− j)) mod (2
m
− 1)
ε
k
Рис. 7.5. Структурная схема деления элементов поля
Так же, как и в случае логарифмического умножителя, устройство или программный алгоритм, реализующие логарифмическую схему операции воз- ведения в степень должны учитывать случай, когда элемент поля ε
i будет равен нулю. Результат при этом также будет равен нулю. Ещё одним исклю- чением является равенство нулю делителя ε
j
. В этом случае алгоритм или схема деления должны выдавать ошибку.
7.2.7. Логарифмы Зеча
В некоторых случаях неудобно производить последовательные преоб- разования элементов поля путем операций логарифмирования и антилога- рифмирования при осуществлении операций над элементами поля. В таком случае может применяться подход, состоящий в использовании логарифмов
Зеча [
2
,
22
].
Логарифм Зеча Z(n) задаётся равенством
ε
Z
(n)
= 1 + ε
n
(7.22)
При использовании этого метода, можно выполнять арифметические операции в конечном поле, работая только с логарифмами и не обращаясь к антилогарифмам.
52