Определение 4.6.7. Любое расширение поля GF (q), в котором многочлен g (х) над GF (q) распадается в произведение линейных множителей и констант, называется полем разложения многочлена g (х).

Теперь у нас есть все необходимое для описания структуры произвольного поля Галуа.

Теорема 4.6.8. Пусть а - примитивный элемент поля Галуа GF (0), являющегося расширением поля GF (q), и пусть т - степень минимального многочлена f {х) элемента а над GF (q). Тогда число элементов в поле равно Q = q"- и каждый элемент р может быть представлен в виде

Р*= a„ ia"-i + а,„ 2а"-2 4-----f аа + «о.

где Gm-i. о.» -элементы поля GF (<?).

Доказательство. Очевидно, что каждый элемент р вида Р = a„ ia»-> + аа- -\-----h la + «о

принадлежит полю GF (Q). Такое разложение единственно, так как если

Р = fe ia«-i + bm-a"- + • • • -f + &о - другое представление элемента р, то

О = (а а - «т-! + ... fej) ос + (Ор - Ь,),

и, следовательно, а является корнем многочлена степени m - 1, что противоречит выбору числа т. Всего имеется q" таких элементов р, и, следовательно, число элементов поля Q не меньше q".

С другой стороны, каждый ненулевой элемент поля может быть представлен в виде некоторой степени элемента а. Но если / (х) - минимальный многочлен элемента а, то / (а) = 0. Следовательно,

а-" + /™ ia- -f • • • + Да + /о = О,

Полученное равенство можно использовать для того, чтобы выразить элемент а™ через сумму меньших степеней элемента а:

сС" = -fm-l"------/l«-/o.

Полученное соотношение можно повторно применять для редукции любой степени элемента а к линейной комбинации степеней (а"-, а\ а"), что дает

= Чш-1 (-/m-icc------/i« - /о) -

-/m-aa"------/ia2-oa.

4.6. структура конечного поля 10?

Й t. д. Следовательно, каждый элемент поля GF (Q) может быть представлен в виде линейной комбинации элементов а*"-, а"~2 ,.., а, а", так что Q не может быть больше q", и теорема доказана. □

Следствие 4.6.9. Каждое поле Галуа содержит р элементов, еде р -некоторое простое, а т -положительное целое число.

Доказательство. Каждое поле Галуа содержит подполе с р элементами, к которому надо применить теорему 4.6.8. □

Заметим, что теорему 4.6.8 можно использовать для того, чтобы связать с каждым элементом поля некоторый многочлен степени не выше т - 1 путем простой замены элемента а на неопределенную переменную х. Эти многочлены можно рассматривать как элементы поля. Складываться и умножаться они будут по модулю минимального многочлена / (х) элемента а. Это в точности то же самое поле, которое получается в теореме 4.4.3, если в качестве простого многочлена выбрать / (х). Следовательно, число элементов в каждом поле Галуа равно степени простого числа, и каждое поле Галуа может быть построено с помощью арифметики по модулю простого многочлена.

Наконец, мы должны доказать и обратное: такое поле существует для каждого простого р и целого положительного числа т. Прежде всего установим некоторые предварительные результаты.

Теорема 4.6.10. Пусть характеристика поля GF (q) равна р. Тогда для любых элементов а и usGF (q) и любого положительного целого т

{а ± P)P" = аР" ±

Доказательство. Предположим, что теорема верна для т = I. Тогда

(а ± 3)Р = аР + Р. Возведем это равенство в р-ю степень: ((а ± Р)Р)Р = («Р ± рр)Р,

и снова используем теорему для т = I:

(а ± 3)р = аР ± ЗР\ Повторяя эту процедуру т - 1 раз, получаем

(а±Р)р" = ар"±Зр".

Следовательно, теорему надо доказать только для т = I. Воспользовавшись биномиальным разложением

(а±)р=Х>(;)аШ)Р-\

видим, что достаточно доказать, что в поле GF (q) выпoЛHяetCй равенство

Но для каждого i

f М . р! . Р(р-1)! \с ) i\{p-i)i г1(р-/)!

йвляется целым числом, ар - простое. Следовательно, знаменатель делит {р - 1)!, а число кратно р. Таким образом,

() = О (mod р), и поскольку арифметикой целых чисел в поле GF (q) является арифметика по модулю р, то в GF (q) биномиальный коэффициент (] = 0. Наконец, если р = 2, то (±Р) = = 3, а если р нечетно, то (± 3)р=+Зр. Это завершает доказательство теоремы. □

Теорема 4.6.11. Пусть р -простое, а т-положительное целое число. Тогда наименьшее поле разложения многочлена g (х) = = -X, рассматриваемого над полем GF (р), содержит р" элементов.

Доказательство. Каждый многочлен над GF (р) имеет наименьшее поле разложения. Пусть GF (Q) - наименьшее поле разложения многочлена g (х) = - х. Тогда в поле GF (Q) многочлен g (х) имеет р" корней (возможно, кратных). Мы покажем, что все р" корней различны и образуют поле. Из этого будет следовать, что GF (Q) содержит элементов.

Для того чтобы доказать, что множество корней образует поле, достаточно показать, что оно замкнуто относительно операций сложения и умножения и содержит обратные для всех ненулевых элементов. Пусть а и 3 - корни многочлена g (х). Согласно теореме 4.6.10,

(а ± Р)р" = аР" ± РР" = а ± Р,

так что а±Р -также корень многочлена, и, следовательно, множество замкнуто относительно операции сложения. Далее,

(аР)р" = аР"-рр" = ар,

и, таким образом, «р тоже является корнем, и множество корней замкнуто относительно операции умножения. Далее, -а является аддитивным обратным элементу а, так что каждый элемент имеет аддитивный обратный. Аналогично легко проверить, что если а - корень многочлена, то -также его корень.