Наконец* проверим, Что все р"* корней многочлена хр"* ~ х различны. Это вытекает из вида формальной производной:

d [хр" - xVdx ((pi) хр"- - 1 - -Ь

так как ((/?)) = О в поле GF (Q). Следовательно; многочлен xi -х не имеет кратных корней. □

Теперь мы получили обращение теоремы 4.6.9,

Следствие 4.6Л2. Для каждого простого р и положительного целого числа т cyu{ecmeyem поле Галуа с р элементами.

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

Теорема 4.6.13, Для каокдого целого положительного т над каждым конечным полем GF (q) существует хотя бы один простой многочлен степени т.

Доказательство. Так как q - степень простого числа, то q" также является степенью простого числа. Согласно следствию 4.6.12, существует поле с q" элементами. Это поле содержит примитивный элемент а, и, по теореме 4.6.8, минимальный многочлен этого элемента а над GF (q) является простым многочленом степени т. □

Следствие 4.6.14. Для каждого целого положительного т над каждым конечным полем GF (q) существует хотя бы один примитивный многочлен степени т.

Доказательство. Пусть а - примитивный элемент поля GF {q"), и пусть / (х) -- минимальный многочлен элемента а над GF (q). Тогда в поле многочленов по модулю f (х) примитивный элемент а = х является корнем многочлена / (х), так что многочлен X представляет собой примитивный элемент поля. □

В заключение главы рассмотрим вопрос о существовании квадратного корня в поле Галуа.

Теорема 4.6.15. Каждый элемент поля GF (2™) имеет в этом поле квадратный корень. Для нечетных простых р половина ненулевых элементов поля GF (р") имеет квадратный корень в GF (р"). Половина ненулевых элементов поля GF (р™) имеет квадратный корень в расширении GF (р™), а не в GF (р").

Доказательство. Так как нулевой элемент имеет квадратный корень в любом поле, то рассматривать надо только ненулевые элементы поля. Сначала рассмотрим полеС (2") характеристики 2 с примитивным элементом а. Тогда порядок элемента а является

нечетным числом. Каждый элемент поля Р может быть записан в виде а для некоторого i, и поэтому - a/, если i четно, и i/p - а(+")/2, если i нечетно. В любом случает/р является элементом поля GF (2").

Рассмотрим теперь поле GF (q), характеристика которого равна простому нечетному числу р, а примитивным элементом является а = 7+, где у - примитивный элемент расширения GF {(f) (порядка q - \ = {q \) {q - 1)) и q -\- \ четно. Так как q равно степени нечетного простого числа. Любой элемент Р может быть записан в виде a или в виде y<?+i) для некоторого L Тогда если i четно, то -j/p = а/2 и принадлежит полю GF (q), а если i нечетно, то -j/p = t+i) /2 принадлежит полю GF (q), но не полю GF (q), так как i (q + 1)/2 в этом случае не кратно + 1.

□

ЗАДАЧИ

4.1. Пусть над GF (2) Pi{x)= I и (х) = х* + + х + 1.

а. Найти НОД Ipix), рАх)1

б. Найти многочлены А {х) w В (х), удовлетворяющие равенству

НОД [pi (х), Ра {х)]=А (X) pi (х) + В (X) Ps (X).

4.2.а. Сколько различных приведенных многочленов второй степени вида л: + ал; + 6, ЬфО, имеется над полем GF (16)?

б. Сколько различных многочленов вида {х - а) {х - Р), а, фО, имеется над полем GF (16)?

. в. Доказывает ли это существование неприводимых многочленов над полем GF (16)? Сколько простых многочленов степени два имеется над полем GF (16)?

4.3. Доказать теорему 4.1.2, связывая обе части равенств с алгоритмом деления. Этим же способом доказать теорему 4.3.4.

4.4.а. Используя алгоритм Евклида, найти НОД (1573, 308). б. Найти целые числа Л и В, удовлетворяющие равенству

НОД (1573,308) = 1573Л + 308В.

4.5. Доказать, что в кольце Z/(15) целых чисел по модулю 15 многочлен р (х) = х - 1 имеет более двух корней. Этот же многочлен над полем имеет два корня. В каком месте не проходит доказательство теоремы в случае кольца?

4.6. Сколько различных приведенных многочленов над GF (2) делят многочлен х - 1?

4.7. Построить поле GF (5), выписав для него таблицы сложения и умножения.

4.8. Построить таблицы сложения и умножения для полей GF (8) и GF (9). 4.9.а. Доказать, что многочлен р (х) = х-j-2 неприводим над полем GF (3).

б. Каковы возможные (мультипликативные) порядки элементов поля

GF (27)?

в. Чему равен порядок элемента х в поле GF (27), построенном по модулю этого многочлена р (х)?

г. Предполагая, что поле GF (27) построено по модулю данного многочлена р {х), найти (2х + I) (х + 2).

4.10. Вычислить 3"" (mod 5).

4.11. Доказать, что кольца отношений Z Ид) и CF {q) [х]1(р {х)) являются кольцами.

4.12. Многочлен р (х) = + д;-f д; + ( неприводим над полем GF (2). Следовательно, кольцо многочленов по модулю р {х) является полем GF (16).

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

б. Показать, ito многочлену л; + 1 соответствует примитивный элемент этого поля.

в. Найти минимальный многочлен элемента x+ 1.

4.13.а. Построить таблицы сложения и умножения поля GF (2), используя неприводимый многочлен -{- х-{- 1 над GF (2).

б. Повторить задачу п. а для многочлена + х- + 1 н доказать, что эти два поля изоморфны. Иначе говоря, доказать, что второе поле можно получить из первого путем переименования его элементов.

4.14. Таблицы сложения и умножения для поля Gf (2) можно построить по меньшей мере двумя следующими способами:

(i) используя неприводимый многочлен степени 4 над CF (2);

(ii) используя неприводимый многочлен степени 2 над GF (4). Построить эти таблицы, используя второй способ.

4.15. Многочлен р [х) ..= д:о + д; + 1 примитивен над полем GF (2) и может быть использован для построения поля GF (1 048 576), в котором элемента, соответствующий многочлену х, будет примитивным.

а. Каковы подполя этого поля?

б. Сколько из этих подполей не имеют никаких собственных подполей, отличных от GF (2)?

в. Вычислить в этом поле выражение аЬ - !, где а = л- -- д: -f- 1 и Ь= х+ х + х.

4.16. Доказать, что для формальной производной многочлена выполняется равенство

\г (X) S (х) ] = г (х) s{x)+r (X) S (х)

и что (х) делит г (х) тогда и только тогда, когда а (х) делит г (х).

4.17. Доказать, что в любом поле характеристики 2 любой элемент Р удовлетворяет условию - Р = р.

ЗАМЕЧАНИЯ

Материал данной главы обычен для математической литературы. Свойства полей Галуа описываются во многих книгах по абстрактной алгебре, например в книгах Биркгофа и Маклейна [1953], а также Ван дер Вардена 1950, 1953]. Однако стандартное изложение является формальным, уделяет основное внимание абстрактным свойствам и содержит мало примеров и приложений. В книге Берлекэмпа [1968] подробно рассматриваются те свойства полей Галуа, которые исполиЗуются в теории кодирования.