Gf(2)

Gf(3)

Рис. 4.1. Примеры конечных полей.

можно вычислять значения многочлена над GF (q) в расширении поля GF (q). Такое вычисление проводится подстановкой элементов из расширения поля вместо неопределенной переменной х и выполнения операций в расширении поля. Например, пусть над GF (2)

р{х); + х+1.

Тогда (см. рис. 4.1) для элементов поля GF (4) имеем

р(0) = 0« + 0+ 1 = 1,

р (1) = Р + 1 + 1 = 1,

р (2) = 23 + 2 + 1 = 2,

р (3) = 3« + 3 + 1 = 3.

Если р (Р) = О, то элемент р называется корнем многочлена р (х) или корнем уравнения р (х) = 0. Многочлен не обязательно имеет корни в свеем собственном поле. Многочлен л: + л: + 1 не имеет корней в GF (2), а также в GF (4).

Теорема 4.3.8. Элемент р является корнем многочлена р {х) тогда и только тогда, когда X - р делит р [х). Более того, корнями многочлена р {х) степени п являются не более п элементов поля.

Доказательство. Согласно алгоритму деления,

p{x) = {x-)Q{x)s{x),

где степень s [х) меньше единицы. Таким образом, s {х) является элементом поля Sq. Следовательно, О = р (Р) = (Р - Р) Q (Р) + + So, и соответственно s {х) = So = 0.

4А. конечные поля; кольца многочленов 95

Обратно, если х - р делит р (х), то

р (х) = {x~)Q (х),

так что р (Р) = (Р - Р) Q (Р) = О, и, таким образом, р - корень многочлена р (х).

Разложим теперь многочлен р (х) в произведение элемента поля и простых множителей. Степень многочлена р (х) равна сумме степеней простых множителей, и для каждого корня имеется один такой множитель. Следовательно, существует не более п корней. □

4.4. КОНЕЧНЫЕ [ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦАХ МНОГОЧЛЕНОВ

Конечные поля можно построить из колец многочленов таким же образом, каким были построены поля из кольца целых чисел. Пусть имеется кольцо многочленов F [х] над полем F. Так же, как были построены для кольца Z кольца отношений, можно построить и кольца отношений для кольца F [х]. Выбирая из F [х] произвольный многочлен р (х), можно определить кольцо отношений, используя р (х) в качестве модуля для задания арифметики этого кольца. Мы ограничимся рассмотрением только приведенных многочленов, так как это ограничение снимает ненужную неопределенность построения.

Определение 4.4.1. Для произвольного приведенного многочлена р (х) ненулевой степени над полем F кольцом многочленов по модулю р {х) называется множество всех многочленов над F, степень которых не превосходит степени многочлена р (х), с операциями сложения и умножения многочленов по модулю р {х). Это кольцо принято обозначать через F {х)/(р (х)).

Произвольный элемент г (х) кольца F [х] можно отобразить в элемент кольца F 1х]/{р (х)) с помощью соответствия г (х) -> -> Rp f,x) [г (х)]. Два элемента а (х) и b (х) из F [х], отображаемые в один и тот же элемент из F [х]/{р (х)), называются сравнимыми:

а {х) = b (х) (mod р (х)).

Тогда b (х) а {х) + Q (х) р (х) для некоторого многочлена Q (х).

Теорема 4.4.2. Множество F 1х]/{р (х)) является кольцом.

Доказательство предоставляется читателю в качестве упражнения. □

Выберем в кольце многочленов над GF (2), например, многочлен р (х) = х + 1. Тогда кольцо многочленов по модулю р (х) равно GF (2) [хУ{х + 1). Оно состоит из элементов {О, 1, х.

•) Напомним, что простой многочлен является одновременно неприводимым и приведенным. Для построения поля достаточно только неприводимости р (х), но мы условились рассматривать только приведенные многочлены, так что дальнейшие результаты носят менее общий характер.

X + \ , х, х + I, + X, х + X + 1\. в этом кольце умножение выполняется, например, следующим образом:

= R.+i [X (хз f 1) + х + X] = х -f X, где использована редукция по правилу х* = л: (л: + 1) +

Теорема 4.4.3. Кольцо многочленов по модулю приведенного многочлена р (х) является полем тогда и только тогда, когда многочлен р (х) прост ) .

Доказательство. Пусть многочлен р (х) прост. Чтобы доказать, что рассматриваемое кольцо образует поле, достаточно показать, что каждый (Ненулевой элемент имеет мультипликативный обратный. Пусть S (х) - некоторый ненулевой элемент кольца. Тогда deg s {х) < deg р (х). Так как многочлен р (х) прост, то НОД Is (х), р (х)] = \. По следствию 4.3.7

I =а{х)р{х) + b (х) S (х)

для некоторых многочленов а (х) и b (х). Следовательно,

i=-Rpwli] = Rp (.) [а{х)р{х)-\-Ь(х) S (х)] =

= Rp W {Rp w lbix)].R, (.) [six)]} = R, {R, [Ь{х)]-8{х)}.

Таким образом, в кольце многочленов по модулю р (х) многочлен Rpix) [b (х)] является мультипликативным обратным к s (х).

Предположим теперь, что степень многочлена р (х) равна по меньшей мере 2 и что он не преет. Тогда р (х) = г (х) s (х) для некоторых г (х) к S (х), степени которых равны по меньшей мере 1. Если кольцо является полем, то многочлен г (х) имеет обратный /~ (л:), и поэтому

s (х) = Rp (.) [s (х)] = Rp м [г~ ix) г (X) S (X)] -

= RpW \Г{х)р(х)]=.

Но s {х) Ф, и мы получаем противоречие. Следовательно, такое кольцо не может быть полем. □

Если над полем GF (q) найден простой многочлен степени п, то, используя развитую в данном параграфе теорию, можно построить поле Галуа, содержащее q" элементов. В этом построении элементы поля представляются многочленами над GF (q) степени не выше п-1. Всего существует q" таких многочленов, и, следовательно, их столько же, сколько элементов в поле.