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

Вычисление суммы элементов поля ε
m и ε
n при использовании логариф- мов Зеча производится по формуле
ε
m
+ ε
n
= ε
m
· (1 + ε
n
−m
) = ε
m
+Z(n−m)
(7.23)
В табл.
7.3
приведен логарифм Зеча в поле GF(2 4
) [
22
].
Таблица 7.3
Логарифм Зеча в поле GF(2 4
), образованном полиномом p(x) = x
4
+ x + 1.
Степень
Логарифм
Степень
Логарифм элемента n
Зеча Z(n)
элемента n
Зеча Z(n)
−∞
0 7
9 0
−∞
8 2
1 4
9 7
2 8
10 5
3 14 11 12 4
1 12 11 5
10 13 6
6 13 14 3
Для примера рассмотрим сложение двух элементов поля GF(2 4
), обра- зованного полиномом p(x) = x
4
+ x + 1:
a
= ε
4
= 1100
и b
= ε
8
= 1010.
В сумме элементы a и b дают элемент c, равный c
= a + b = ε
4
+ ε
8
= 1100 + 1010 = 0110 = ε
5
Теперь рассчитаем элемент c через логарифм Зеча (табл.
7.3
) по формуле
(
7.23
):
c
= ε
4
+ ε
8
= ε
4+Z(8−4)
= ε
4+Z(4)
= ε
4+Z(4)
= ε
4+1
= ε
5
Можно видеть, что результаты, полученные с помощью сложения посред- ством логарифмирования и антилогарифмирования, и результаты расчета че- рез логарифм Зеча совпадают.
53

7.3. Алгоритмы для проведения расчетов в двоичных полях Галуа и их реализации
7.3.1. Алгоритм обращения элемента поля на основе расширенного алгоритма Евклида
Алгоритм Евклида для двух полиномов предназначен для определения их наибольшего общего делителя (НОД), а расширенный алгоритм Евклида позволяет найти два полинома u(x) и v(x), удовлетворяющих формуле (
7.24
)
[
25
]:
НОД(a(x), b(x)) = u(x)a(x) + v(x)b(x).
(7.24)
Алгоритм обращения элемента поля, представленного полиномом a(x),
показан в алг.
7.1
[
25
].
Алгоритм 7.1. Алгоритм обращения элемента поля на основе расширенного алгоритма Евклида
1
s
(x) = p(x); // p(x) — образующий полином поля
2
r
(x) = a(x);
3
v
(x) = 0;
4
u
(x) = 1;
5
while deg(r(x)) 6= 0 do
6
δ = deg(s(x)) − deg(r(x));
7
if δ < 0 then
8
s
(x) r(x);
9
v
(x) u(x);
10
δ = −δ ;
11
end
12
s
(x) = s(x) + x
δ
r
(x);
13
v
(x) = v(x) + x
δ
u
(x);
14
end
Result: u(x) = a
−1
(x)
Утверждается [
26
], что данный алгоритм быстрее прочих алгоритмов обращения элементов поля [
25
].
В качестве примера рассмотрим процедуру нахождения обратного эле- мента для элемента поля Галуа GF(2 3
), образванного порождающим полино- мом p(x) = x
3
+ x + 1. Выберем элемент поля a(x) = ε
4
= x
2
+ x (табл.
7.2
).
Начальные значения:
s
(x) = p(x) = x
3
+ x + 1; v(x) = 0;
r
(x) = a(x) = x
2
+ x;
u
(x) = 1;
Шаг 1:
deg(r(x)) > 0;
δ = deg(s(x)) − deg(r(x)) = 3 − 2 = 1;
s
(x) = s(x) + x
δ
r
(x) = (x
3
+ x + 1) + x(x
2
+ x) = x
2
+ x + 1;
v
(x) = v(x) + x
δ
u
(x) = 0 + x · 1 = x;
54

Шаг 2:
δ = deg(s(x)) − deg(r(x)) = 2 − 2 = 0;
s
(x) = s(x) + x
δ
r
(x) = (x
2
+ x + 1) + (x
2
+ x) = 1;
v
(x) = v(x) + x
δ
u
(x) = x + 1;
Шаг 3:
δ = deg(s(x)) − deg(r(x)) = 0 − 2 = −2 < 0 ⇒ s(x)
r(x), v(x) u(x);
s
(x) = x
2
+ x;
r
(x) = 1; ⇒ deg(r(x)) = 0; // завершаем работу v
(x) = 1;
u
(x) = x + 1;
δ = −δ = 2;
s
(x) = s(x) + x
δ
r
(x) = (x
2
+ x) + x
2
· 1 = x;
v
(x) = v(x) + x
δ
u
(x) = 1 + x
2
(x + 1);
Результат: a
−1
(x) = u(x) = x + 1 = ε
3 7.3.2. Алгоритм умножения двух элементов поля
«сдвиг-со-сложением, справа-налево»
Данный алгоритм реализует умножение двух элементов поля, представ- ленных в виде полиномов, в поле Галуа GF(2
m
), образованном полиномом p
(x). Приведенное название является калькой с англоязычного обозначения данного алгоритма: «right-to-left shift-and-add field multiplication». Этот алго- ритм основан на том, что a
· b = a m
−1
x m
−1
b
+ . . . + a
2
x
2
b
+ a
1
xb
+ a
0
b
На каждом шаге i в этом алгоритме вычисляется произведение x i
b mod p(x)
и полученное складывается с произведением c при условии, что a i
= 1, как показано в алг.
7.2
[
26
].
Алгоритм 7.2. Алгоритм умножения двух элементов поля
«сдвиг-со-сложением, справа-налево»
Data: Двоичные полиномы a(x) и b(x) степени ≤ m − 1 1
if a
0
= 1 then
2
c
(x) = b(x);
3
else
4
c
(x) = 0;
5
end
6
for i =
1 . . . m − 1 do
7
b
(x) = x · b(x) mod p(x);
8
if a i
= 1 then
9
c
(x) = c(x) + b(x);
10
end
11
end
Result: c(x) = a(x)b(x)
mod p(x)
55

Для примера рассмотрим перемножение двух элементов поля, пред- ставленных в виде полиномов a(x) и b(x), над полем GF(2 4
), образованного полиномом p(x) = x
4
+ x + 1:
a
(x) = x
2
+ 1 = 1010 = ε
8
;
b
(x) = x
2
+ x = 0110 = ε
5
Поскольку a
0
= 1, c(x) = b(x) = x
2
+ x.
Шаг 1:
b
(x) = x · b(x) mod p(x) = x
3
+ x
2
;
a
1
= 0 ⇒ переход на следующий шаг
Шаг 2:
b
(x) = x · b(x) mod p(x) = (x · (x
3
+ x
2
)) mod p(x) = x
3
+ x + 1;
a
1
= 1 ⇒ c(x) = c(x) + b(x) = (x
2
+ x) + (x
3
+ x + 1) = x
3
+ x
2
+ 1;
Шаг 3:
b
(x) = (x · (x
3
+ x + 1)) mod p(x) = x
2
+ 1;
a
1
= 0 ⇒ завершаем
Результат: c(x) = x
3
+ x
2
+ 1 = 1011 = ε
13
Считается, что этот алгоритм хорошо подходит для аппаратной реализации на логических элементах, где сдвиг вектора b реализуется за один такт, и ме- нее применим для программной реализации из-за значительного числа таких сдвигов [
26
].
7.3.3. Алгоритм Карацубы–Офмана умножения двух элементов поля
Этот алгоритм изначально предназначен для умножения длинных чисел.
Он был предложен в 1960 г. А. А. Карацубой и опубликован в 1962 г. в сборни- ке докладов АН СССР [
27
]. Этот алгоритм позволил уменьшить оценку слож- ности умножения n-значных чисел с O(n
2
) до O(n log
2 3
). Позднее данный ал- горитм было предложено использовать для умножения элементов конечного поля, представленных в виде полиномов [
28
]. Далее будем говорить именно об алгоритме умножения двух элементов поля.
В разных источниках этот алгоритм может называться и как алгоритм
Карацубы–Офмана, и как просто алгоритм Карацубы [
28
,
29
].
Обычно выделяют два варианта алгоритма Карацубы–Офмана. Первый вариант алгоритма — это так называемый 2
k n
-битный умножитель. Он пред- назначен для работы с элементами поля GF(2
m
), где m = rn, r = 2
k
[
28
].
56

Множители A и B, принадлежащие полю GF(2
m
), представляются в виде полиномов через левый степенной базис формулой [
28
,
29
]:
A
(x) =
m
−1
∑
i
=0
a i
x i
=
m
−1
∑
i
=
m
2
a i
x i
+
m
2
−1
∑
i
=0
a i
x i
=
= x m
2
m
2
−1
∑
i
=0
a i
|
m
2
x i
+
m
2
−1
∑
i
=0
a i
x i
= x m
2
A
H
+ A
L
,
B
(x) =
m
−1
∑
i
=0
b i
x i
=
m
−1
∑
i
=
m
2
b i
x i
+
m
2
−1
∑
i
=0
b i
x i
=
= x m
2
m
2
−1
∑
i
=0
b i
|
m
2
x i
+
m
2
−1
∑
i
=0
b i
x i
= x m
2
B
H
+ B
L
(7.25)
Каждый из полученных полиномов A
H
(x), A
L
(x), B
H
(x), B
L
(x) имеет сте- пень в два раза меньшую нежели исходные множители A(x) и B(x).
Исходя из формулы (
7.25
), произведение C = A · B можно представить в виде формулы [
28
,
29
]:
C
(x) = (x m
2
A
H
+ A
L
)(x m
2
B
H
+ B
L
) =
= x m
A
H
B
H
+ (A
H
B
L
+ A
L
B
H
)x m
2
+ A
L
B
L
=
= x m
A
H
B
H
+ A
L
B
L
+ (A
H
B
H
+ A
L
B
L
+
+(A
H
+ A
L
)(B
H
+ B
L
))x m
2
= x m
C
H
+C
L
(7.26)
Необходимо сразу отметить, что полином-произведение C(x), получен- ный в результате вычисления по алгоритму Карацубы–Офмана, имеет длину до 2m − 1 двоичных элементов. Следовательно, чтобы определить элемент по- ля C ∈ GF(2
m
), равный A · B, необходимо привести полином C(x) по модулю образующего многочлена поля p(x) [
28
,
29
].
Далее введем две переменные, как показано в формуле [
28
,
29
]:
M
A
= A
H
+ A
L
,
M
B
= B
H
+ B
L
(7.27)
В соответствии с формулой (
7.26
), для вычисления произведения C необхо- димо провести четыре операции сложения
M
A
= A
H
+ A
L
,
M
B
= B
H
+ B
L
,
R
= A
H
B
H
+ A
L
B
L
,
R
+ M
A
M
B
и три операции умножения
A
H
B
H
,
A
L
B
L
,
M
A
M
B
,
57

каждую из которых также можно разбить вышеописанным способом [
28
,
29
].
Процедура умножения повторяется рекурсивно пока не будут получены однобитные множители, произведение которых вычисляется за одну опера- цию умножения (конъюнкция). Количество итераций не превышает dlog
2
(m)e.
На практике для умножения элементов поля большой степени часто приме- няют схему, в которой алгоритм Карацубы–Офмана используется для умень- шения длины операндов до значения, при котором удобно применить какой- либо из быстрых алгоритмов умножения, который был бы слишком сложен для реализации при применении его к операндам большой длины [
28
].
Алгоритм 2
k n
-битного умножителя Карацубы–Офмана представлен в алг.
7.3
[
28
,
29
].
Алгоритм 7.3. Алгоритм 2
k n
-битного умножителя Карацубы–Офмана
Data: Элементы поля A, B ∈ GF(2
m
), где m = rn = 2
k n
, и множители A и B
могут быть представлены в виде A = x m
2
A
H
+ A
L
и B = x m
2
B
H
+ B
L
соответственно.
1
Procedure
Kmul2
k
(C, A, B)
2
if r =
1 then
3
C
= A · B;
4
return;
5
end
6
for i =
0 . . . (
r
2
− 1) do
7
M
Ai
= A
L
i
+ A
H
i
;
8
M
Bi
= B
L
i
+ B
H
i
;
9
end
10
Kmul
2
k
(C
L
, A
L
, B
L
);
11
Kmul
2
k
(M, M
A
, M
B
);
12
Kmul
2
k
(C
H
, A
H
, B
H
);
13
for i =
0 . . . (r − 1) do
14
M
i
= M
i
+C
L
i
+C
H
i
;
15
end
16
for i =
0 . . . (r − 1) do
17
C
r
2
+i
= C
r
2
+i
+ M
i
;
18
end
19
end
Result: Полином C(x) = A(x) · B(x) длиной до 2m − 1 элементов, где
C
(x) = x m
C
H
+C
L
Вторым вариантом использования алгоритма Карацубы–Офмана явля- ется так называемый двоичный умножитель Карацубы, предназначенный для работы с полями Галуа GF(2
m
) произвольной степени m [
28
,
29
].
Алгоритм двоичного умножителя Карацубы представлен в алг.
7.4
Необходимо заметить, что двоичный умножитель Карацубы использует внут- ри себя 2
k n
-битный умножитель (алг.
7.3
) [
28
,
29
].
58

Алгоритм 7.4. Алгоритм двоичного умножителя Карацубы
Data: Элементы поля A, B ∈ GF(2
m
), где m — любое целое, и множители A и B
могут быть представлены в виде A(x) = x m
2
A
H
+ A
L
и B(x) = x m
2
B
H
+ B
L
соответственно.
1
Procedure
BK(C, A, B)
2
k
= blog
2
(m)c;
3
d
= m − 2
k
;
4
if d =
0 then
5
Kmul
2
k
(C, A, B);
6
return;
7
end
8
for i =
0 . . . (d − 1) do
9
M
Ai
= A
L
i
+ A
H
i
;
10
M
Bi
= B
L
i
+ B
H
i
;
11
end
12
Kmul
2
k
(C
L
, A
L
, B
L
);
13
Kmul
2
k
(M, M
A
, M
B
);
14
BK
(C
H
, A
H
, B
H
);
15
for i =
0 . . . (2k − 2) do
16
M
i
= M
i
+C
L
i
+C
H
i
;
17
end
18
for i =
0 . . . (2k − 2) do
19
C
k
+i
= C
k
+i
+ M
i
;
20
end
21
end
Result: Полином C(x) = A(x) · B(x) длиной до 2m − 1 элементов, где
C
(x) = x m
C
H
+C
L
Аппаратная реализация умножителя Карацубы, как можно видеть из формул и алгоритмов, требует использования блоков умножения (операция
«И») и сложения по модулю два («Исключающее ИЛИ»). На рис.
7.6
приведе- ны схемы одноразрядного и двухразрядного умножителей Карацубы. Можно видеть, что однобитный умножитель представляет из себя обычный блок «И»
с двумя входами [
30
].
a
0
b
0
c
0
(а)
a
0
a
1
b
0
b
1
c
0
c
1
c
2
(б)
Рис. 7.6. Схемы умножителей Карацубы:
(а)
одноразрядный умножитель;
(б)
двухразрядный умножитель
59

На рис.
7.7
приведена схема четырехразрядного умножителя Карацубы,
в состав которого входят три двухразрядных умножителя, которые на схеме обозначены как KM2 [
30
].
KM2
KM2
KM2
a
0
a
2
a
1
a
3
b
3
b
1
b
2
b
0
c
3
c
2
c
4
c
1
c
5
c
0
c
6
Рис. 7.7. Схема четырехразрядного умножителя Карацубы
7.3.4. Умножитель двух элементов поля по схеме
Рейхани-Мазолеха
Данная реализация умножителя была предложена в начале 2000-х чле- нами IEEE А. Рейхани-Мазолехом и М. А. Хасаном. Являясь модификацией умножителя Мастровито, эта схема позволяет построить эффективный умно- житель с параллельной структурой для двоичных полей Галуа, построенных с использованием порождающего многочлена определённого вида [
31
].
Для рассмотрения умножителя вводится ряд обозначений.
Элементы поля GF(2
m
), являющиеся множителями, обозначаются как A
и B. Множитель A можно представить как сумму
A
=
m
−1
∑
i
=0
a i
ε
i
, a i
∈ {0, 1},
где ε
i
— элементы левого степенного базиса поля GF(2
m
).
Элементы a i
можно представить в виде вектора a = [a
0
, a
1
, . . . , a m
−1
]
T
В таком случае, множитель A можно представить как произведение векторов
A
= εεε
T
a, где εεε = [1, ε, . . . , ε
m
−1
]
T
. Аналогично можно представить и множи- тель B.
B
=
m
−1
∑
j
=0
b j
ε
j
= εεε
T
b,
где b = [b
0
, b
1
, . . . , b m
−1
]
T
60

Вводится понятие приведенной матрицы Q размера m − 1 × m, которая является двоичной матрицей, получаемой из тождества
ε
ε
ε
↑
≡ Qεεε(mod(p(ε))),
(7.28)
где εεε
↑
= [ε
m
, ε
m
−1
, . . . , ε
2m−2
]
T
Каждому неприводимому полиному p(x) соответствует одна и только одна приведенная матрица Q [
31
].
Также вводятся два вектора d и e, являющиеся функциями от A и B,
соответственно [
31
]:
d = Lb и
e = Ub,
(7.29)
где L — нижнетреугольная матрица Теплица размера m × m, а U — верхне- треугольная матрица Теплица размера (m − 1) × m, которые представлены в формуле:
L
,








a
0 0
0 0
· · · 0
a
1
a
0 0
0
· · · 0
a
2
a
1
a
0 0
· · · 0
a m
−2
a m
−3
· · · a
1
a
0 0
a m
−1
a m
−2
· · · a
2
a
1
a
0








,
U
,






0 a m
−1
a m
−2
· · ·
a
2
a
1 0
0
a m
−1
· · ·
a
3
a
2 0
0
· · ·
0
a m
−1
a m
−2 0
0
· · ·
0 0
a m
−1






(7.30)
Результат C произведения элементов поля A и B получается из следую- щей формулы:
c = d + Q
T
e,
(7.31)
где c = [c
0
, c
1
, . . . , c m
−1
]
T
Используя формулы (
7.29
), (
7.30
) и (
7.31
), можно построить эффектив- ный умножитель двух элементов двоичного поля Галуа GF(2
m
), общая архи- тектура которого представлена на рис.
7.8
[
31
].
Можно видеть, что умножитель состоит из двух крупных блоков: IP- сети
1
и Q-сети. В IP-сети производится расчет элементов векторов d и e согласно формуле (
7.29
). IP-сеть состоит из блоков циклического сдвига
(рис.
7.9(а)
) и m блоков I
i
, каждый из которых, кроме последнего блока I
m
−1
,
состоит из двух ячеек IP. Блок I
m
−1
состоит из одной ячейки IP(m). Струк- тура ячеек IP показана на рис.
7.9(б)
. В Q-сети производится вычисление по
1
IP-сеть — от англ. Inner Product — внутреннее (скалярное) произведение
61

формуле (
7.31
). Q-сеть состоит из m блоков BTX
2
, структура которых пока- зана на рис.
7.9(б)
[
31
].
IP
(m)
IP
(1)
IP
(m − 1)
IP
(2)
IP
(m − 2)
IP
(1)
IP
(m − 1)
I
m
−1
I
m
−2
I
1
I
0
Цикл.
сдвиг
Цикл.
сдвиг
Цикл.
сдвиг
B
A
d
0
d
1
d m
−2
d m
−1
IP-сеть
IB
e
0
e
1
e m
−2
BT X
m
−1
BT X
m
−2
BT X
1
BT X
0
d
0
d
1
d m
−2
d m
−1
c m
−1
c m
−2
c
1
c
0
Q-сеть
Рис. 7.8. Архитектура умножителя двух элементов двоичного поля Галуа GF(2
m
) по схеме Рейхани-Мазолеха
Для некоторых типов образующих поле Галуа полиномов p(x) суще- ствуют определенные формы матрицы Q, которые позволяют построить ее,
не прибегая к сложным расчетам [
31
].
В качестве примера можно привести равномерно распределенные по- линомы
3
, под которыми понимаются неприводимые полиномы вида p
(x) = x ns
+ x
(n−1)s
+ . . . + x s
+ 1,
(7.32)
образующие поле Галуа GF(2
m
) с m = ns [
31
].
2
BTX — от англ. Binary Tree of XOR’s — двоичное дерево элементов XOR
3
В англ. литературе используется термин Equally Spaced Polynomial (s-ESP)
62

Цикл.
сдвиг
A
=
a m
−1
a
0
a
1
(а)
a
0
b m
−1
a m
−2
b
1
a m
−1
b
0
· · ·
c i
1 2 · · · dlog
2
m e
Блок BTX
Ячейка IP(m)
(б)
Рис. 7.9. Элементы умножителя по схеме Рейхани-Мазолеха:
(а)
блок циклического сдвига;
(б)
пример ячейки IP(m) и блока BTX
На рис.
7.10
в графическом виде показаны матрицы Q для трех типов равномерно распределенных полиномов. Черными квадратами показаны по- зиции ненулевых элементов в матрице Q [
31
].
0
s
2s m
− s m − 1 0
s m
− 2
· · ·
(а)
0
m
− 1 0
1
m
− 2
(б)
0
m
/2
m
− 1 0
m
/2
m
− 2
(в)
Рис. 7.10. Графическое представление матрицы Q для трех типов равномерно распределенных полиномов p(x) = x ns
+ x
(n−1)s
+ . . . + x s
+ 1, m = ns:
(а)
1 < s <
m
2
;
(б)
s
= 1 (все коэфф. равны 1);
(в)
s
=
m
2
(трином)
Другими образующими полиномами, имеющими характерную форму матрицы Q, являются полиномы из трех элементов — триномы:
p
(x) = x m
+ x k
+ 1,
k
< m,
(7.33)
включающие в себя и равномерно распределенный трином с k =
m
2
, показан- ный на рис.
7.10(в)
. Прочие типы триномов представлены на рис.
7.11
[
31
].
Еще более сложную форму матрицы Q имеют образующие полиномы,
состоящие из пяти элементов — пентаномы:
p
(x) = x m
+ x k
3
+ x k
2
+ x k
1
+ 1,
1 ≤ k
1
< k
2
< k
3
≤ m − 1.
(7.34)
Матрицы Q для некоторых типов пентаномов можно найти в [
31
].
63

0 1
m
− 1 0
m
− 2
(а)
0
k m
− 1 0
m
− k m
− 2
(б)
0
k m
− 1 0
m
− k
2(m − k)
r
(m − k)
m
− 2
(в)
0
m
− 1 0
m
− 2
(г)
Рис. 7.11. Графическое представление матрицы Q для различных типов триномов p
(x) = x m
+ x k
+ 1:
(а)
k
= 1;
(б)
1 < k <
m
2
;
(в)
m
2
< k < m − 1, r = b m
−2
m
−k c;
(г)
k
= m − 1
В качестве примера рассмотрим построение умножителя для поля Га- луа GF(2 4
), образованного полиномом p
(x) = x
4
+ x + 1.
Этот полином является триномом (
7.33
) с k = 1. Следовательно, его матрица
Q строится по схеме, представленной на рис.
7.11(а)
, и имеет вид
Q =


1 1 0 0 0 1 1 0 0 0 1 1


Множители A и B представляются векторами a = [a
0
, a
1
, a
2
, a
3
]
T
,
b = [b
0
, b
1
, b
2
, b
3
]
T
64