Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
251
D2 + D + 1. Для того чтобы а10 было корнем D2 + D + 1, должно выполняться а20 + а10+ 1 =0. Так как а15 = 1, то а20 = а5, что приводит к соотношению а10 + а5 -f 1 = 0; складывая многочленные представления а10, а5 и 1, получаем, что утверждение действительно верно.
Для практического выполнения операций в произвольном поле Галуа GF (рт) обычно удобно представлять элементы поля как многочлены по модулю примитивного многочлена т-й степени над GF (р); с точки зрения реализации это означает представление каждого элемента в виде последовательности т элементов в GF (р). Как было показано, сложение в GF (рт) при этом соответствует сложению соответствующих последовательностей в GF (р). Умножение на специально
Рис. 6.6.5. Умножение элементов поля a(t) и b(t) в поле многочленов по модулю f(t).
выбранный элемент а = t также выполняется устройством, представленным на рис. 6.6.4. И, наконец, умножение двух произвольных элементов поля может производиться устройством, изображенным на рис. 6.6.5.
Вначале при выполнении умножения этим устройством регистр g пуст, a a (t) и b (/) находятся в регистрах а и b соответственно. Затем регистры b и g сдвигаются на одну позицию вправо таким образом, что в регистре g будет многочлен bm-\0. (t). Затем регистры 6 и g вновь сдвигаются вправо. После этого в регистре g будет храниться R f(t) + bm-2) а (?)]. После т сдвигов регистров g и b в реги-
стре g будет Rut) [b (t)a (?)], или элемент поля b (t)*a (t). Следует заметить, что для выполнения этим устройством умножения в GF (рт) необходимые время и сложность оборудования прямо пропорциональны т.
Существование полей Галуа
Как было показано, поля Галуа существуют только, когда число элементов равно степени простого числа, и существует (с точностью до нумерации элементов) с любым заданным числом элементов только одно поле. В последующих трех теоремах доказывается, что для любого 252
рп поле Галуа GF (рп) действительно существует. Собственно, все, что нужно доказать — это существование неприводимых многочленов всех степеней над GF (р) для всех простых чисел р >¦ 1.
Теорема 6.6.6. Пусть аир — элементы поля GF (рп) с характеристикой р. Тогда при всех целых т ^ 1
(a + p)pm = apm + ppm. (6.6.8)
Докаазтельство. При m = 1 из разложения бинома следует, что (a + |J)*’ = a*’ + paP-1p+...+ ^ р оР-‘Р + ... + Р', (6.6.9)
где ^ р ) ap~l Р1 нужно рассматривать как сумму ^ р j слагаемых, каждое из которых равно а/’~1р1. Вместе с тем при —1
р)_ р (р 1)! (6.6.10)
i ) г! (р—»')!
Так как — целое число, а р — простое число, то знаменатель
(6.6.10) является делителем (р—1)!; поэтому р является делителем
Следовательно, при сложении 1 с самой собой раз получим 0
и все внутренние слагаемые в правой части (6.6.9) равны 0; таким образом,
(а + ру' = а/’ + р*. (6.6.11)
Возводя (6.6.11) в степень р, получаем
(а + Р)р2 = (ар + рр)р — ар2 + ррг;
аналогично, возводя (т — 1) раз соотношение (6.6.11) в степень р, получаем (6.6.8). |
Следствие.. Если
f(D)= 2 /гD1
i = 0
— многочлен над GF (р) и а — элемент поля GF (рп), то при любом т >- 0
f(aPm) = [f(a)]Pm. (6.6.12)
В частности, если a — корень /(D), то при любом т ^ 0
f(aPOT) = 0. (6.6.13)
Доказательство. Имеем
i — i
Т fia‘
t = о
/1—1 \рт
-W' + lSfiOt) =
253
= 23 (// *Ym 23 ffa.!Pm. (6.6.14)
,- = o ,¦ = о
Так как ft — элемент GF (p), to /f_I = 1, поэтому /? = /;. Последо’ вательно возводя обе части равенства в степень р, получаем ff1 = ft. Поэтому (6.6.14) преобразовывается к виду
i
[/(а)Гт= 23 fi<y-ipm^f(ocpm)- (6.6.15)
i — 0
Если / (а) = 0, то получаем (6.6.13). [
Теорема 6.6.7. Пусть / (D) — нормированный неприводимый многочлен п-й степени над GF (р). Многочлен Dp"1 — 1 делится на / (D) тогда и только тогда, когда т делится на п.
Доказательство. Рассмотрим поле GF (рп) многочленов над GF (р) по модулю / (/). Многочлен t является элементом рассматриваемого поля; обозначим этот элемент через а. Так как / (а) = 0, то а — корень / (D). Любой другой элемент в этом поле можно представить в виде
(3 = i0 -f- li сс -f-... -J- i an~ *, (6.6.16)
где i0....i„_i —целые элементы поля. Выберем i0, ..., in_2 таким об-
разом, чтобы |3 было примитивным элементом; обозначим через В (D) соответствующий ему многочлен В (D) = i0 + iiD -j- ... + i„_, Dn l, так что p = В (а). Теперь предположим, что Dp”1 — 1 делится на / (D). Тогда а является корнем D^n~x — 1 и
