Кольцо полиномов GF(pk) является расширением понятия поля вычетов по модулю простого числа р. Здесь элементами поля являются не числа, а полиномы (многочлены) k - ой степени от фиктивной переменной х, имеющие вид:
Q(х) = akÄxk Å ak- 1 Äxk- 1 Å... Å a 1 Äx Å a 0,
где коэффициенты аÎGF(p) = {0, 1,..., p -1}.
Переменной x можно не придавать особого смысла. Она введена для образования степеней, делающих возможным непосредственное сложение (приведение по модулю р) только членов одинаковой степени. Знак Ä (умножение по модулю р) для упрощения записи опускается.
Полиномы можно складывать и умножать, соблюдая правила действий по модулю р. Примеры при р = 5:
(4 x 2 Å 3) Å (x 3 Å 3 x 2 Å 2 x Å 2) = x 3 Å 2 x 2 Å 2 x;
(4 x2 Å 3) Ä (3 x 3 Å 2 x) = 2 x 5 Å 2 x 3 Å x.
Как и при умножении полиномов обычной алгебры, степени перемножаемых членов складываются. Полиномы над GF(p) можно делить с остатком или нацело, если определить для коэффициентов операцию вычитания по модулю р. Пример деления без остатка при р = 5:
2 x 5 Å 2 x 3 Å x ½ 4 x 2 Å 3
- 2 x 5 Å 4 x 3 3 x 2 Å 2 x
3 x 3 Å x
-3 x 3 Å 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).
