Составители:
числами, а многочлен х
3
+ 2х
2
+ х приводим, поскольку может быть
представлен как х (х + 1)(х + 1).
Многочлен, который в данном поле является образующей, называют
примитивным, все его коэффициенты взаимно просты.
Арифметические действия над коэффициентами a
i
выполняются по
модулю q, а наивысшая степень x равна (n - 1), так как выполняется
приведение по модулю многочлена p(x), имеющего степень n.
Особый интерес представляют поля GF(2
n
), где коэффициентами a
i
являются 0 и 1. Поэтому многочлен a(x) степени не выше (n -1) можно
представить как вектор из n двоичных цифр: a
n-1
a
n-2
…a
1
a
0.
Каждый из n – битовых векторов соответствует конкретному
элементу поля GF(2
n
).
Например, GF(2
3
) включает следующие элементы: 0, 1, х, х +1, х
2
, х
2
+ 1,
х
2
+ х, х
2
+ х + 1, которым соответствует двоичная форма: 000, 001,010, 011,
100, 101, 110, 111.
Вычисления в полях Галуа предполагают знания следующих
основных свойств многочленов:
1. Ненулевые элементы поля GF(2
n
) являются корнями обобщенного
многочлена x
2
n
-1
+ 1.
2. Каждый многочлен p(x) степени n, неприводимый над полем
GF(2), является делителем двучлена x
2
n
-1
+1, и каждый его делитель,
неприводимый над полем GF(2), имеет степень, равную n и менее.
3. Все элементы поля GF(2
n
) можно получить как совокупность
остатков от деления 1000…00 на неприводимый многочлен p(x),
входящий в разложение двучлена x
2
n
-1
+ 1. Эти остатки - корни двучлена
x
2
n
-1
+ 1, обращающие его в нуль.
Число остатков равно 2
n
– 1.
4. В поле GF(2
n
) существует примитивный элемент g такой, что
каждый ненулевой элемент поля GF(2
n
) может быть представлен как
некоторая степень g, т.е. мультипликативная группа GF(2
n
) является
циклической.
Достоинства вычислений в поле GF(2
n
):
162
Страницы
- « первая
- ‹ предыдущая
- …
- 158
- 159
- 160
- 161
- 162
- …
- следующая ›
- последняя »
