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

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

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

 

Произвольный элемент r(х) кольца F[х] можно отобразить в элемент кольца РF[х]/(р (х)) с помощью соответствия r(х) —RР (Х) [r (х)]. Два элемента a(х) и b(х) из F[х], отображаемые в один и тот же элемент из F[х]/(р(х)), называются сравнимыми:

а(х) = b(х) (mod p(х)).

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

Теорема 2.4.2.Множество F1х]/(р (х)) является кольцом.

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

 

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

{0, 1, х,, x+1,x2 ,x2 +1, х2 + х, х2 + х + 1}. В этом кольце умножение выполняется, например, следующим образом:

( x2 +1 ) (x2)= Rx3+1 (( x2 +1 ) (x2)) = Rx3+1 (( x3 +1 ) x + x2 +x ) = x2 +x ,

где использована редукция по правилу х4 = х (х3 + 1) + х.

 

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

Доказательство.Пусть многочлен р (х) прост. Чтобы доказать, что рассматриваемое кольцо образует поле, достаточно показать, что каждый ненулевой элемент имеет мультипликативный обратный. Пусть s(х) —некоторый ненулевой элемент кольца. Тогда deg s(х) < deg р(х). Так как многочлен р (х) прост, то НОД [s(x), р (х)] = 1. По следствию 2.3.7

НОД [s(x), р (х)] = 1 =a(х)р(х) + b(х) s (х)

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

1 = Rр(х)[1] = Rр(х)[a(х)р(х) + b(х) s (х)]= Rр(х){ Rр(х)[a(х)р(х)} + Rр(х)[b(х) s(x)}} = Rр(х){ Rр(х)[b(х) s(x)}} = Rр(х){Rр(х)[b(х)} Rр(х)[ s(x)}} = Rр(х){Rр(х)[b(х)} s(x)}

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

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

 

s(x) = Rр(х)[s(х)}= Rр(х)[ r-1(х) r(x) b(х)}= Rр(х)[ r-1(х) p(x) }= 0

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

 

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

 

 

Многочлене обозначения Двоичные обозначения Целочисленные обозначения Степенные обозначения
x x+1 x0 x1 x2

 

a) б)

 

 

+ 0 1 x x+1 * 0 1 x x+1
x x+1 0 1 x x+1 0 1 0 x+1 x 1 x x+1 0 1 x x+1 x 1 0 x+1 0 0 0 0 0 1 x x+1 0 x x+1 1 0 x+1 1 x  

 

б)

Рис. 2.2. Структура поля GF(4). а представления поля GF(4); б—арифме­тические таблицы.

 

В качестве примера построим поле GF(4) по полю GF (2), используя примитивный многочлен р(х) = х2 + х + 1. Перебирая все возможные разложения, легко проверить неприводимость этого многочлена. Элементы поля задаются многочленами {О, 1, х , х+ 1). Приведенные на рис. 2.2 таблицы сложения и умножения строятся по готовым правилам. Конечно, после того как арифметические таблицы построены, можно заменить многочленные обозначения на целочисленные или другие желаемые обозначения.. Таблица 2.1 содержит список простых многочленов над GF(2). Одним из способов проверки простоты этих многочленов является метод проб и ошибок, т. е. непосредственная проверка всех возможных разложений, хотя для многочленов высоких степеней для этого потребуется ЭВМ. Собранные в табл. 2.1 простые многочлены представляют собой специальные частные случаи простых многочленов, известных под названием примитивных многочленов. Как будет описано в следующем параграфе, они дают наиболее уУдобное представление расширения поля.

В заключение параграфа подытожим, где мы находимся. Мы разработали необходимые для получения полей построения, которые будут использованы в дальнейшем, но для полного понимания предмета необходимы еще некоторые сведения. В частности, необходимо установить следующие факты: 1) над каждым полем Галуа существуют простые многочлены любой заданной степени; 2) разработанные построения достаточны для получения всех

 

 

Таблица 2.1

Простые многочлены над GFОР (2)