Алгебра полиномов над полем Галуа. Изоморфизм алгебры полиномов и множества кодов с поразрядным сложением.

Кольцо полиномов GF(p^k) является расширением понятия поля вычетов по модулю простого числа р. Здесь элементами поля являются не числа, а полиномы (многочлены) k - ой степени от фиктивной переменной х, имеющие вид:

Q(х) = a_kÄx^k Å a_{k- 1} Äx^{k- 1} Å... Å a ₁ Äx Å a ₀,

где коэффициенты аÎGF(p) = {0, 1,..., p -1}.

Переменной x можно не придавать особого смысла. Она введена для образования степеней, делающих возможным непосредственное сложение (приведение по модулю р) только членов одинаковой степени. Знак Ä (умножение по модулю р) для упрощения записи опускается.

Полиномы можно складывать и умножать, соблюдая правила действий по модулю р. Примеры при р = 5:

(4 x ² Å 3) Å (x ³ Å 3 x ² Å 2 x Å 2) = x ³ Å 2 x ² Å 2 x;

(4 x² Å 3) Ä (3 x ³ Å 2 x) = 2 x ⁵ Å 2 x ³ Å x.

Как и при умножении полиномов обычной алгебры, степени перемножаемых членов складываются. Полиномы над GF(p) можно делить с остатком или нацело, если определить для коэффициентов операцию вычитания по модулю р. Пример деления без остатка при р = 5:

2 x ⁵ Å 2 x ³ Å x ½ 4 x ² Å 3

- 2 x ⁵ Å 4 x ³ 3 x ² Å 2 x

3 x ³ Å x

-3 x ³ Å x

Проще всего операции с полиномами выполняются при р = 2, так как операции сложения и вычитания по модулю 2 дают одинаковый результат, и вводить отдельную операцию вычитания не нужно. Кроме того, умножение на множестве {0, 1} очень просто. Знак Ä и коэффициенты 0 и 1 не пишутся.

Примеры операций с полиномами над полем GF (2). Умножение:

(х ³ Å х)(х ² Å х Å 1) = х ⁵ Å х ⁴ Å х ² Å х;

Деление с остатком: х ⁴ Å х ³ Å 1 ½ х ² Å 1.

Å х ⁴ Å х ² х ² Å х Å 1

х ³ Å х ² Å 1

Å х ³ Å х.

х ² Å х Å 1

Å х ² Å 1

х - остаток R (х)

Приведенные здесь примеры дают представление о полиномах над GF(p) и о действиях над ними при различных модулях р.

Перейдем к определению кольца полиномов над GF(p). Для того, чтобы вместо бесконечного множества полиномов всевозможных степеней получить конечное и при этом замкнутое множество, нужно задаться некоторым полиномом Q (х) степени k и использовать его так, как в числовом кольце используется число р, а именно - в качестве модуля, по которому приводится результат операции.

Если элементами числового кольца являются числа от 0 до р -1, т.е. остатки от деления произвольного целого числа на р, то элементами кольца полиномов будут остатки от деления произвольных полиномов высоких степеней на полиномиальный модуль Q (х).

Зададимся полиномом второй степени над GF (2)

Q (х)= х ² Å 1.

Множество остатков от деления на Q (х) должно содержать все полиномы степени меньше двух, так как любой полином более высокой степени будет делиться на Q(X) с остатком или без него. В данном случае множество остатков определяется легко: М = {0, 1, х, х Å1}.

Используя этот список составим таблицы Кэли для сложения и умножения по модулю Q(X) (табл. 8.7 и 8.8).

Исследование таблиц показывает, что по сложению получается абелева группа, а по умножению группа не получается, так как в последней строке таблицы 8.8 нет единицы, иначе говоря, для х Å1 нет обратного элемента.

Таблица 8.7 Таблица 8.8

Å			х	х Å1		Ä			х	х Å1
			х	х Å1
			х Å1	х					х	х Å1
х	х	х Å1				х		х		х Å1
х Å1	х Å1	х				х Å1		х Å1	х Å1

В числовом кольце подобный результат получался при составном числе р, а здесь причина состоит в том, что принятый нами полиномиальный модуль разлагается на сомножители:

Q (х) = х ² Å 1 = (х Å 1)(х Å 1).

Для получения поля полиномов над GF (2) нужно взять в качестве модуля Q (х) не разлагающийся на сомножители, т.е. неприводимый полином, например

Q (х) = х ² Å х Å 1.

Множество остатков будет таким же, но группа теперь будет получаться не только по сложению, но и по умножению (табл.8.9).

Таблица 8.9

Ä			х	х Å1
			х	х Å1
х		х	х Å1
х Å1		х Å1		х

Аналогично получаются кольца и поля полиномов над GF(p) при других р и при различных степенях полиномиального модуля вычетов.

Для прикладных теорий очень важно, что множеству полиномов, образующих расширенное поле Галуа GF(p^k), изоморфно поле р -ичных чисел длиной до k разрядов по операциям поразрядное сложение и поразрядное умножение по mod p.

Степени фиктивной переменной х при этом заменяются степенями основания системы счисления. иначе говоря, любому полиному из GF(р^k) однозначно соответствует р -ичное число, цифры которого равны соответствующим коэффициентам полинома.

Например: полиному 2 х ⁵ Å х ⁴ Å 2 над GF (3) соответствует троичное число 210002.

Эта простая связь между алгебраическим выражением и позиционным числом позволяет описывать формулами самые различные преобразования цифровых кодов. Например, сдвиг влево на два разряда с приписыванием справа двух нулей выражается умножением на х ².

Сложение, умножение и деление полиномов над GF(p) можно заменить операциями над числами. Например при р = 2 умножение и деление цифровых кодов по правилам, определенным для полиномов:

11011 110011 ½ 101

Ä 101 Å 101 1111

11011 110

Å 11011 Å 101

1110111 111

Å 101

Å 101

дает результаты, не сводимые к обычному сложению и умножению чисел. В приведенных здесь примерах обычные операции (при переводе в десятичную систему) давали бы 27´5 = 135 вместо 119 (1110111) и 51:5 = 10 ¹/₅ вместо 15 (1111).