Составители:
Такие конечные поля называют полями Галуа и обозначают GF(q
n
)
или GF(q) при n = 1.
Вычисления в полях Галуа широко используются в
криптографии. В нем работает вся теория чисел, в поле содержатся
числа только конечного размера, при делении отсутствуют ошибки
округления. В поле Галуа определены четыре алгебраические
операции. При этом операции сложения и вычитания выполняются
по модулю 2. Операция умножения элементов поля
выполняется
как умножение по модулю неприводимого многочлена p(x) (то
есть многочлена, по модулю которого построены элементы поля
GF(2
n
)).
Чтобы выполнить деление элемента b на элемент a в поле
GF(2
n
) по модулю p(x), сначала находят обратный элемент
a
-1
(mod p(x)), а затем вычисляют b a
-1
(mod p(x)).
Каждый двоичный вектор длины n, исключая 0, является взаимно
простым с неприводимым многочленом p(x) независимо от
значения p(x). Поэтому число вычетов взаимно простых с p(x)
равно ϕ(p(x)) = 2
n
– 1. Поэтому a
-1
= a
ϕ(p(x))-1
mod p(x) = a
2n-2
mod p(x).
В настоящее время многие криптосистемы основываются на полях
Галуа, основанных на арифметике по модулю неприводимых
многочленов степени n, чьи коэффициенты – целые числа по модулю q,
где q – простое. Эти поля Галуа обозначают как GF(q
n
). Они имеют
элементы, которые описываются многочленами степени не выше (n - 1)
в форме
a(x) = a
n-1
x
n-1
+…+ a
1
x + a
0
.
Каждый элемент a(x) является вычетом по модулю p(x), где p(x) –
неприводимый многочлен степени n (то есть p(x) нельзя разложить на
сомножители – многочлены степени меньше n).
Многочлен называют неприводимым, если его нельзя представить
как произведение двух других многочленов (конечно, кроме 1 и
самого многочлена). Многочлен х
2
+ 1 неприводим над целыми
161
Страницы
- « первая
- ‹ предыдущая
- …
- 157
- 158
- 159
- 160
- 161
- …
- следующая ›
- последняя »
