4.412. Теорема. Порядок конечного поля равен степени его характеристики.

Доказательство. Предположим, что поле имеет порядок q и характеристику р. Согласно теореме 4.24, в поле содержится примитивный элемент а порядка q - i- Число сопряженных с а элементов равно мультипликативному порядку числа р по модулю q - 1; обозначим это число через т. Так как q - 1 делит jo"* - 1, тод - lp"- 1 и 9 Так как степень а равна т,

то все многочлены от а, степени которых меньше т, различны и q. Следовательно, q = р"*. щ

Если уже показано, что каждый элемент х поля порядка q удовлетворяет уравнению а;?"" = х, то = = ж, или

х - X. Следовательно, используя индукцию по ге, получаем другое обобш;ение теоремы Ферма.

4.413. Теорема. Каждый элемент поля порядка q удовлетворяет равенству а;" = х при любом п.

Множество классов вычетов по модулю заданного неприводимого многочлена / {х) степени d над полем порядка q образует поле порядка q. Если обозначить через а класс вычетов, содержащий х, то / (а) = 0. Таким образом, хотя / {х) неприводим над полем порядка q, в поле порядка q он имеет корень. Так как а является элементом поля порядка q, то, согласно теореме 4.413, а""* - а = О для любого п. Кроме того, элемент а удовлетворяет уравнению / (а) = 0. Следовательно, а является общим корнем многочленов а;"** - х и / (а;). Тогда а;" - аг = (а;) / (а;) + г [х), где степень остатка г {х) меньше степени d многочлена / (а;). В частности, полагая а; = а, получаем, что а" - а = (а) / (а) + г (а) или 0=04-" Но все многочлены от а, степени которых меньше и, представляют собой различные элементы поля порядка так что из соотношения г (а) = О следует, что г {х) = 0. Это доказывает теорему 4.414.

4.414. Теорема. Если к кратно d, то каждый неприводимый многочлен степени d над полем порядка q делит а: - х. [ Например, каждый неприводимый двоичный многочлен степени 1 или 3 должен делить аг" - х. Произведение всех неприводимых! двоичных многочленов степеней 1 и 3 равно а: (а: -- 1) (а:* + а; -f 1) X « X (а: -f- а; + 1). Это произведение также должно делить з? -\- х.\ Так как степень этого произведения равна 8, то должно выполнять-; ся равенство х {х -\- \) {з? х -\- 1) (а: + а; -f 1) = х + х, кото- рое легко проверить с помощью непосредственных вычислений. В общем случае произвольного поля порядка q произведение всех! различных нормированных неприводимых многочленов, степенж!

которых делят к, является делителем многочлена x - х. Степень х - X равна , степень произведения всех различных нормированных неприводимых многочленов, степени которых делят к, равна сумме степеней всех этих многочленов. Для каждого т, делящего &, имеется различных нормированных неприводимых многочленов степени т. Следовательно, степень произведения всех различных нормированных неприводимых многочленов, степени которых делят к, равна 2 1т- Согласно теореме 3.35, это число равно q и, сле-

довательно, получаем

4.415. Теорема. Произведение всех неприводимых нормированных многочленов над полем порядка q, степени которыхделят к, равно х - X.

В частности, над полем вычетов mod р многочлен а; - х распадается в произведение всех нормированных неприводимых многочленов, степени которых делят к. В поле порядка р многочлен х - X разлагается в произведение р линейных множителей. Так как поле вычетов mod р - подполе поля порядка р, то приравнивая эти два разложения в поле порядка р, получаем

4.416. Теорема. Если f {х) - многочлен степени т над полем вычетов по модулю р и т делит к, то поле порядка р должно содержать т корней многочлена f {х).

Из этого результата можно вывести единственность конечного ноля порядка р. Для доказательства этого факта рассмотрим некоторый конкретный неприводимый многочлен / (х) степени к над простым полем. Любое конечное поле порядка р содержит к корней / (х). Если обозначить через а один изэтих корней, то каждый элемент поля может быть представлен в виде многочлена от а степени << к. Это дает теорему 4.417.

4.417. Теорема. Для каждого простого числа р и произвольного к существует единственное конечное поле порядка р. Это поле называется полем Галуа порядка р и обозначается через GF {р).

С точки зрения прикладника такое подчеркивание факта единственности поля GF (р) вводит в заблуждение, так как это поле, как мы видели в примере разд. 4.5, может иметь много различных представлений. Конструкция и стоимость оборудования, реализующего вычисления в GF {р), существенно зависят от выбора представления поля. Поэтому некоторые инженеры предпочитают рассматривать различные представления GF {р) как различные поля.

Эта точка зрения, в частности, оправдана в ситуациях, при которых переход от одной формы представления к другой дает большой выигрыш.

Нормированные неприводимые многочлены, степени которых делят к, образуют подмножество множества нормированных неприводимых многочленов, степени которых делят /, тогда и только тогда, когда 7 кратно к. Следовательно, если q - некоторая степень простого числа, то справедлива

4,418. Теорема. Поле GF {<) является подполем поля GF (q) тогда и только тогда, когда j кратно к.

Если / {х) - неприводимый многочлен степени т над полем GF (д), то каждый корень / (х) лежит в GF (q). Если w - один из таких корней, то все корни совп?1дают с w, wt . . ., и>ч"~. Эти элементы называются д-сопряжеиными с w. Если q - степень простого числа р, то д-сопряженные элементы составляют подмножество соответствующих /?-сопряженных элементов.

4.5. Примеры

В качестве непосредственной иллюстрации рассмотренных теорем исследуем разложение двоичного многочлена х* - х:

X* - X = х(х ~ 1} xQi) (х) з> (х) = х(х - \) (х" +Х + 1). Это разложение справедливо над любым полем. Над двоичным полем» (полем из двух элементов) + и - взаимозаменяемы и потому

х - X = х{х + i) {х" + X + 1). Множитель х + X + 1 является неприводимым двоичным многочле-,» ном второй степени. Для разложения этого неприводимого многочле-! на надо расширить поле так, чтобы включить корни многочлена.; Если обозначить через \ один из его корней, то

2 + + 1 = О или 2 = + 1. Другой корень этого квадратного многочлена, а именно является! двоично сопряженным с %. Обозначим его через д. В GF (4) имеег полное разложение

X* -х = х{х + \){х + 1) (х1+ д).

Здесь

д = 1 + \ = 1 1==д + \==д\

Четыре элемента поля могут быть представлены как четыре двоичнь многочлена от (или д), степени которых < 2; три ненулевых эл« мента поля могут быть представлены в виде соответствующих ст* пеней I (или д).

В качестве более поучительного примера рассмотрим разложение двоичного многочлена а;* - а; и несколько связанных с ним представлений поля GF (16). Начнем с разложения на круговые многочлены:

= xQ(l)(x) Q(3)(a:) Q(5)(x) Q<15) (гс)

= X(X-1) (x2-fx-fl) (x44-x3 + x2-f X+ 1) (xS-xf-f X5-X + X3-X+ I).

Ото разложение справедливо над любым полем. Читателю предлагается проверить, что

((15) [х) 3? - х + х" - Х + 3? - X + \.

в двоичном поле многочлен Q) распадается на два примитивных )1сприводимых квадратных многочлена Одним из методов определения этих множителей является метод исключения. Оба множителя могут быть записаны в виде х* + Аз? + Вх + Са; + 1, где А, В и С - двоичные числа. Так как 1 не является корнем многочлена, то должно выполняться условие А + 5 + С = 1, так что либо все три коэффициента А, В, С, либо только один из них равны 1. Первый случай исключается, так как приводит к (?() {х). Наконец,

так что

х* + х2 + 1 = (а;2 -I- х -Ь if,

{х) = {Х + 3? + \){Х + Х + 1).

Более простой метод определения двух неприводимых делителей многочлена Q() {х) базируется на том факте, что если и GF (q) и ж £ GF (Oi то преобразование хх -\- и переводит сопряженные элементы в сопряженные и неприводимые многочлены в неприводимые. Например, в рассматриваемом случае многочлен Ql (х) неприводим, и, значит, неприводим многочлен {х + 1) = (х + 1)* + + {х + \Г + {х + 1Г + {x + i)+ 1 = (х* + 1) + (х« + + + X + 1) + {х + I) + {х + I) + i = X* + х + I. Так как этот неприводимый трехчлен не делит Q> {х), то он должен делить (/15) (х). Другой делитель многочлена Q) (х) есть многочлен .r (х~* + х~ -\- \) = х + + i, взаимный с этим делителем. Любой из методов дает следующее разложение над GF (2):

х< - X = X {х + I) {х + X + 1) {х* + х + х + X + 1) X X {х + а? + \){х + х + 1). Расширяя двоичное поле присоединением I, я д, корней многочлена

1) Следуя Диксону [1901] и Алберту [19561, все кодовики-теоретики определяют сейчас примитивный многочлен степени т как неприводимый делитель многочлена Q (з""" над GF (q). Согласно классической терминологии, которой придерживаются многие математики, примитивным называется целочисленный многочлен со взаимно простыми коэффициентами.

8-658

Таблица 4.1

+ X + I, получим поле GF (4). Разложение над GF (4) имеет вид

x-x = x(x + i)ix + l){x + d) {х + + X X {х + dx + i) {х + 1х + 1) {х + дх + д){х + х + 1) X

Х{х + Х + д).

Читатель должен отметить, что и 5 появляются в разложении сопряженньпии парами аналогично тому, как при разложении действительных многочленов на комплексные множители появляется пара + i и -г. Происходит это по той же причине. Комплексно сопряженные числа +i и -i представляют собой корни одного и того же действительного неприводимого многочлена х + \; VI д сопряжены, поскольку они являются корнями одного и того же неприводимого двоичного многочлена х -\- х -\- I.

Очевидно, что х* - х распадается над GF (4) на четыре неприводимых линейных и шесть неприводимых квадратных множителей; читатель может проверить это методом исключения.

Для последующего разложения необходимо дальнейшее расширение поля до GF (16), дающее те 12 элементов поля GF (16), которые не входят в GF (4). Не ограничивая обпщости, обозначим эти дополнительные 12 элементов различными греческими буквами:

-х=х Qn){x) Я<зцх)

=Х (х+1) (Х2+Ж+1)

(х+1) (Ж2+Ж+1)

=х (х+1) (х+)(ж+а)

Q(6)(x)

(xi+xs+x2+x+l) (xi+ix+mxi+dx+i)

qnb)(x)= (эс8+х7+эсб+ж4+ж8+зс+1)=

(x*+x3+l)(xt+x+i)= (xi+lx+l)(xi+ex+8) (x2+x+l)(xi+x+d)

=x (x+1) {д:+)(ж+а) (ж+в)(ж+ц)(х+7)(ж+в) (х+Р)(ж+у)(х+Л){х+Е)(х+а)(х+я)(х+ч>)(ж+р).

Так как а - один из восьми корней многочлена (?() (х), то он примитивный элемент и каждый из 15 ненулевых элементов поля может быть записан в виде степени а. Эти результаты приведены в столбцах 1 и 2 таблицы 4.1.

Так как а - корень неприводимого над GF (4) квадратного многочлена х + х + , то каждый элемент поля GF (16) можно