Лекции по дискретной математике, страница 6

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

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

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

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

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

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

( x² +1 ) (x²)= R_x3₊₁ (( x² +1 ) (x²)) = R_x3₊₁ (( x³ +1 ) x + x² +x ) = x² +x ,

где использована редукция по правилу х⁴ = х (х³ + 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) найден простой многочлен степени п, то, используя развитую в данном параграфе теорию, можно по­строить поле Галуа, содержащее qⁿ элементов. В этом построении элементы поля представляются многочленами над GF(q) степени не выше (п -1). Всего существует qⁿ таких многочленов, и, следова­тельно, их столько же, сколько элементов в поле.

a)

б)

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

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

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

Таблица 2.1

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

Степень Простые многочлены

2 x² +x +1

3 x³ +x +1

4 x⁴ +x +1

5 x⁵ +x² +1

6 x⁶ +x +1

7 x⁷ +x³ +1

8 x⁸ +x⁴ +x³ +x² +1

9 x⁹ +x⁴ +1

10 x¹⁰ +x³ +1

11 x¹¹ +x² +1

Примечание. Все многочлены являются примитивными.

полей Галуа —других полей нет (Математическая строгость требует здесь большего формализма, и надо было бы сказать, что нет других полей с точностью до изоморфизма. Неформально это означает, что любые два поля Галуа с одинаковым числом элементов являются двумя различными представлениями одного и того же поля. Иллюзия другой структуры может быть, например, создана перестановкой тех же самых символов.) ; 3) в каждом поле имеются некоторые предпочтительные, так называемые примитивные эле­менты.

На рис. 2.3 дается сводка наиболее существенных результатов, относящихся к полям Галуа. Остальная часть главы посвящена

Рис. 2.3. Некоторые основные свойства полей Галуа.

доказательству большинства из этих результатов и введению новых понятий. Доказательство существования примитивных многочленов мы откладываем до конца § 2.5.3.

2.5. ПРИМИТИВНЫЕ ЭЛЕМЕНТЫ

В предыдущем параграфе было построено поле GF(4). На рис. 2.2 видно, , за исключением нуля, все элементы поля могут быть представлены в виде степени элемента х.

Определение 2.5.1. Примитивным элементом поля GF(q) называется такой элемент α, что все элементы поля, за исключением нуля, могут быть представлены в виде степени элемента α.

Например, в поле GF(5) 2¹ =- 2, 2² = 4, 2³ = 3, 2⁴ = 1, так что 2 является примитивным элементом поля GF(5). Примитивные элементы полезны при построении полей, так как если один из них найден, то, перемножая степени этого примитивного элемента, можно построить таблицу умножения в поле. В данном параграфе будет доказано, что каждое поле содержит примитивный элемент.

Поле образует абелеву группу двояким способом. Множество всех элементов поля образует абелеву группу по сложению, и множество всех элементов поля, исключая нуль, образует абелеву группу по умножению. Мы будем работать с группой по умножению. Согласно теореме 1.2.5, порядок этой группы делится на порядок каждого ее элемента

Теорема 2.5.2. Пусть β₁, β₂, … β_q-1 поля ненулевые элементы GF (q); тогда

x^q-1 -1 =(x- β₁) (x- β₂ ) …(x- β_q-1)

Доказательство. Множество ненулевых элементов поля GF(q) образует конечную группу по умножению. Пусть β, — какой-либо ненулевой элемент из GF(q), и пусть h — порядок этого элемента по умножению. Тогда, согласно теореме 1.2.5, h делит q — 1. Следовательно,

β ^q-1= (β^h)^(q-1)/h=(1)^(q-1)/h=1

так что β является корнем многочлена (x^q-1 -1)

Теорема 2.5.3. Группа ненулевых элементов поля GF(q) по умножению является циклической.

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

_s

: q-1=∏ p_i^νi

ⁱ⁼¹

Так как GF(q) — поле, то среди его q-1 ненулевых элементов должен найтись хотя бы один, не являющийся корнем многочлена

x^{(q-1)/ рi}-1 поскольку этот многочлен может иметь не более (q-1)/p_i корней. Следовательно, для каждого i можно найти такой ненулевой элемент а_i поля GF(q), что

(qⁱ-1)/p_i^νi _s

α_i^{(q-1)/ рi}≠1. Пусть b_i= а_i -1 и пусть b = ∏=bi. Докажем. что порядок b равен q-1