Алгебра полиномов над полем Галуа. Изоморфизм алгебры полиномов и множества кодов с поразрядным сложением.
Кольцо полиномов GF(pk) является расширением понятия поля вычетов по модулю простого числа р. Здесь элементами поля являются не числа, а полиномы (многочлены) k - ой степени от фиктивной переменной х, имеющие вид:
Q(х) = akÄxk Å ak-1Äxk-1 Å ... Å a1Äx Å a0,
где коэффициенты аÎGF(p) = {0, 1, ..., p -1}.
Переменной x можно не придавать особого смысла. Она введена для образования степеней, делающих возможным непосредственное сложение (приведение по модулю р) только членов одинаковой степени. Знак Ä (умножение по модулю р) для упрощения записи опускается.
Полиномы можно складывать и умножать, соблюдая правила действий по модулю р. Примеры при р = 5:
(4x2 Å 3) Å (x3 Å 3x2 Å 2x Å 2) = x3 Å 2x2 Å 2x;
(4x2 Å 3) Ä (3x3 Å 2x) = 2x5 Å 2x3 Åx.
Как и при умножении полиномов обычной алгебры, степени перемножаемых членов складываются. Полиномы над GF(p) можно делить с остатком или нацело, если определить для коэффициентов операцию вычитания по модулю р. Пример деления без остатка при р = 5:
2x5 Å 2x3 Å x ½ 4x2 Å 3
- 2x5 Å 4x3 3x2 Å 2x
3x3 Å x
-3x3 Å x
Проще всего операции с полиномами выполняются при р = 2, так как операции сложения и вычитания по модулю 2 дают одинаковый результат, и вводить отдельную операцию вычитания не нужно. Кроме того, умножение на множестве {0, 1} очень просто. Знак Ä и коэффициенты 0 и 1 не пишутся.
Примеры операций с полиномами над полем GF(2). Умножение:
(х3 Åх)(х 2 Å хÅ 1) = х5 Å х4 Å х2 Åх;
Деление с остатком: х4 Å х3 Å 1 ½ х2 Å 1 .
Å х4 Å х2 х2 Å хÅ 1
х3 Å х2 Å 1
Å х3 Å х.
х2 Å х Å 1
Å х2 Å 1
х - остаток R(х)
Приведенные здесь примеры дают представление о полиномах над GF(p) и о действиях над ними при различных модулях р.
Перейдем к определению кольца полиномов над GF(p). Для того, чтобы вместо бесконечного множества полиномов всевозможных степеней получить конечное и при этом замкнутое множество, нужно задаться некоторым полиномом Q(х) степени k и использовать его так, как в числовом кольце используется число р, а именно - в качестве модуля, по которому приводится результат операции.
Если элементами числового кольца являются числа от 0 до р-1, т.е. остатки от деления произвольного целого числа на р, то элементами кольца полиномов будут остатки от деления произвольных полиномов высоких степеней на полиномиальный модуль Q(х).
Зададимся полиномом второй степени над GF(2)
Q(х)= х2 Å 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(х) = х2 Å 1 = (х Å 1)(х Å 1).
Для получения поля полиномов над GF(2) нужно взять в качестве модуля Q(х) не разлагающийся на сомножители, т.е. неприводимый полином, например
Q(х) = х2 Å х Å 1.
Множество остатков будет таким же, но группа теперь будет получаться не только по сложению, но и по умножению (табл.8.9).
Таблица 8.9
| Ä | х | хÅ1 | ||
| х | хÅ1 | |||
| х | х | хÅ1 | ||
| хÅ1 | хÅ1 | х |
Аналогично получаются кольца и поля полиномов над GF(p) при других р и при различных степенях полиномиального модуля вычетов.
Для прикладных теорий очень важно, что множеству полиномов, образующих расширенное поле Галуа GF(pk), изоморфно поле р -ичных чисел длиной до k разрядов по операциям поразрядное сложение и поразрядное умножение по mod p.
Степени фиктивной переменной х при этом заменяются степенями основания системы счисления. иначе говоря, любому полиному из GF(рk) однозначно соответствует р -ичное число, цифры которого равны соответствующим коэффициентам полинома.
Например: полиному 2х5 Å х4 Å 2 над GF(3) соответствует троичное число 210002.
Эта простая связь между алгебраическим выражением и позиционным числом позволяет описывать формулами самые различные преобразования цифровых кодов. Например, сдвиг влево на два разряда с приписыванием справа двух нулей выражается умножением на х2.
Сложение, умножение и деление полиномов над 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 1/5 вместо 15 (1111).