3.3. Поля Галуа GF(p^r)

Мы уже сталкивались с конечными полями порядка , где — простое число, например с классами вычетов по модулю . Однако в многочисленных приложениях нам понадобятся числовые поля порядка и в этом разделе мы узнаем, как их построить и как производить в них вычисления. Сейчас читателю целесообразно заново просмотреть материал разд. 2.3.2, в частности теоремы с 2.3.17 по 2.3.21, и также разд. 3.1.4.

3.3.1. Основные факты о конечных полях

Из определения мы уже знаем, что каждое поле — область целостности; обратное утверждение в общем случае неверно, в чем можно убедиться на примере кольца Z. Однако для конечных полей имеет место

Теорема 3.3.1. Каждая конечная область целостности — поле.

Доказательство. Пусть — конечная область целостности. Если — два элемента из , то для всех ненулевых элементов с в J по правилу-сокращения (см. также теорему -2.3.8). Поэтому для некоторого а это означает, что каждый ненулевой элемент области J имеет в ней мультипликативный обратный, и, значит, J — поле.

Следующие две теоремы непосредственно вытекают из теорем гл. 2. Значения q будут определены позже теоремой 3.3.6; оно не может быть произвольным.

Теорема 3.3.2. Если F — поле из q элементов и а — любой его ненулевой элемент, то

Доказательство. Ненулевые элементы поля F образуют абелеву группу порядка относительно умножения (см. также теорему 2.3.17).

Следствие 3.3.3. Если F — поле из q элементов, то любой элемент удовлетворяет уравнению

Доказательство. Из теоремы 3.3.2 мы знаем, что все ненулевые элементы поля F удовлетворяют уравнению нулевой элемент поля, 0, удовлетворяет уравнении) Поэтому все элементы поля удовлетворяют уравнению

Теорема 3.3.4. Пусть F — поле из q элементов и а — его произвольный ненулевой элемент. Если — порядок элемента а, то

Доказательство. Если не делит , то мы можем найти к и , такие, что , где . Тогда акпаг следовательно, поскольку Это, однако, невозможно, так как — наименьшее число, такое, что Поэтому

В разд. 3.1.4 мы уже видели, что, отправляясь от мы построили новое поле, где — неприводимый полином над (Предположим временно, что для любого существуют неприводимые над полиномы степени ; этот факт мы докажем позже в этом же разделе.) Это новое поле, которое является множеством классов полиномов по модулю содержит четыре элемента и обозначается также . Кроме того, мы можем представлять элементы поля как полиномы с коэффициентами из вычисленные в точке рассматриваемой как корень полинома т.е. это новое поле построено добавлением к единственного элемента, и, значит, является простым расширением поля и обозначается Имеет место следующая

Теорема 3.3.5. Пусть — простое число и — неприводимый полином степени в поле Тогда классы вычетов образуют поле из элементов, содержащее и корень полинома

Доказательство. Локазательство фактически было дано при обсуждении примера в разд.

Теорема 3.3.6. Пусть F — поле из q элементов. Тогда где — простое, а - натуральное числа.

Доказательство. По определению F имеет единичный элемент относительно умножения; мы обозначим его 1. Очевидно, что принадлежит F, и мы обозначаем этот элемент 2. Мы продолжаем

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

Следуя аргументам, представленным в конце разд. 2.1.3 (еще раз просмотрите их), предположим, что

где следовательно, . Значит, должно существовать наименьшее целое число , такое, что аналогично рассуждениям из теоремы 2.3.12 заключаем, что — простое число и, таким образом, — подполе поля F, изоморфное полю (покажите это).

Определим линейную независимость множества элементов из поля F с коэффициентами из поля очевидным образом (см. приложение в конце книги). Среди всех линейно независимых подмножеств поля F пусть — подмножество с максимальным числом элементов. Если а — элемент поля F, то — линейно зависимое множество, т.е. имеются коэффициенты такие, что — линейная комбинация элементов Очевидно, имеется различных линейных комбинаций элементов и это доказывает теорему.

Обратное к этому предложению см. в теореме 3.3.19.

Следствие 3.3.7. Если F — конечное поле, то оно имеет характеристику для некоторого простого и, таким образом, содержит подполе, изоморфное полю

Как мы знаем из разд. 2.3.2, групповой элемент а является примитивным элементом, или примитивным корнем, если его степени пробегают все элементы группы (см. также теорему 2.3.20); примеры также исследовались в разд. 2.3.2. Следующая теорема гарантирует нам, что в каждом конечном поле есть примитивный корень.

Теорема 3.3.8 (теорема о примитивном корне). Пусть F — поле из q элементов. Тогда существует элемент а G F, такой, что каждый ненулевой элемент поля F является степенью элемента а, и порядок элемента а равен

Доказательство. Из теоремы 3.3.4 нам известно, что порядок элемента о делит Идея доказательства состоит в изучении множества О порядков элементов поля F. Очевидно, что О — некоторое множество целых чисел и доказательство будет закончено, когда мы покажем, что принадлежит О. Это так, потому что тогда для некоторого и никакая меньшая степень а не равна 1. То есть будет доказана часть теоремы. Часть тогда легко следует из того, что все степени различны, и, таким образом, они пробегают все ненулевые элементы поля F. Подробности можно найти в книгах (Berlekamp, 1968) или (Childs, 1979).

Теорема 3.3.8 не дает нам никакой формулы для нахождения примитивного корня в поле — простое число. Фактически никакой такой формулы не существует. Известно, однако, что если — простое число вида где q — простое число, то 2 — примитивный корень поля Таким образом, 2 — примитивный корень полей для и т.д. Примитивные корни в конечном поле легко можно найти с помощью следующего метода [обнаруженного в работе (Albert, 1958)].

Нахождение примитивного корня в конечном поле.

В конечном поле элемент а является примитивным корнем, если и только если

для всех простых делителей числа

Обобщением теоремы 3.3.5 получается следующая

Теорема 3.3.9. Пусть F — поле и — (нормированный) полином из Тогда существует содержащее F поле К, такое, что в полином разлагается в произведение линейных сомножителей.

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

Поле К, определенное в теореме 3.3.9, называется полем расщепления для Например, согласно основной теореме алгебры, С — поле расщепления для любого полинома из

Пример. В полином неприводим. Он имеет корень в а именно 21/3, но К не является полем расщепления для потому что

а второй сомножитель имеет два комплексных корня.

Пусть F — поле и К — поле, содержащее F. Предположим, что — корень некоторого ненулевого полинома Тогда мы говорим, что элемент а алгебраичен над F. (Числа, не являющиеся алгебраическими, называются трансцендентными; примеры трансцендентных над Q чисел — )

Теорема 3.3.10. Пусть элемент алгебраичен над F. Тогда существует единственный нормированный неприводимый полином такой, что а является его корнем, и каждый полином с корнем а делится на

Локазательство. Используя принцип полного упорядочения множества степеней полиномов из с корнем а, мы заключаем, что имеется ненулевой нормированный полином наименьшей степени, для которого а является корнем. Методом от противного покажем, что полином неприводим. То есть предположим, что где Тогда и, поскольку К не содержит делителей нуля, или или . Однако это и есть требуемое противоречие, поскольку а является теперь корнем полинома степени, меньшей, чем Поэтому полином неприводим. Наконец, пусть — любой полином в с корнем а. Применяя теорему о делении, получаем где Поскольку , то — нулевой полином и, следовательно,

Полином определенный в теореме 3.3.10, называется минимальным полиномом элемента а над F, потому что из доказав тельства мы знаем, что это полином минимальной степени в с корнем а.

В гл. 4 нам понадобится нахождение минимальных полиномов. Следующая теорема утверждает, что они существуют, и показывает, как их находить.

Теорема 3.3.11. Пусть простое расширение поля F, где минимальный полином элемента а над F имеет степень . Тогда, если 0 — произвольный элемент поля К, то алгебраичен над F и минимальный полином элемента 0 над F имеет степень

Локазательство. Мы знаем, что каждый элемент поля — полином от а степени То же верно для любой степени элемента Чтобы найти минимальный полином элемента над F, будем искать ненулевое решение уравнения

Заменяя степени элемента 0 эквивалентными им полиномиальными выражениями от а и собирая коэффициенты при одинаковых степенях а, мы получаем систему уравнений от неизвестных. Мы используем затем результат из линейной алгебры (см. приложение в конце книги), что любая система однородных линейных уравнений от неизвестных имеет ненулевое решение, чтобы найти в ненулевой полином степени с корнем

Пример. Пусть — неприводимый над полином, и рассмотрим Тогда и поле К состоит из полиномов от а степени 2 с коэффициентами в Чему равен минимальный полином элемента над

Чтобы найти ненулевое решение уравнения выразим степени 0 в виде полиномов от (а ) и получим ) . Пользуясь тем, что (проверьте это), и собирая коэффициенты при одинаковых степенях а, получаем систему

которую решаем в . Решением будет и поэтому минимальный полином элемента над равен .

Некоторые сокращения при выполнении вычисления вручную читатель может найти в книге (Berlekamp, 1968, pp. 112-117). Следующий результат играет существенную роль.

Теорема 3.3.12. Для данных простого числа и натурального числа все конечные поля из элементов изоморфны.

Доказательство. Пусть F — конечное поле из q элементов. Тогда из теоремы 3.3.2 нам известно, что порядок произвольного ненулевого элемента а делит т.е. для Умножая последнее равенство на а, получаем что выполняется и для Поэтому все элементы поля F, являются корнями полинома Следовательно, поскольку полином делится на он должен делиться на — Из равенства степеней следует, что следствия 3.3.7 видно, что поле F получается из присоединением всех корней полинома и поэтому определено единственным образом с точностью до изоморфизма.

Как результат теорем 3.3.5 и 3.3.12 мы имеем такие следствия:

Следствие 3.3.13. Любое конечное поле изоморфно простому расширению поля для некоторого простого числа .

Следствие 3.3.14. Если q не является степенью простого числа , то не существует конечного поля из q элементов.

Доказательство. Если F — конечное поле, то оно изоморфно Для некоторого неприводимого полинома степени . Тогда имеет элементов, и то же верно для

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

Теорема 3.3.15. В любом поле характеристики выполняется соотношение

Доказательство. Раскрывая скобки, получаем Доказательство теперь немедленно следует из того, что коэффициенты делятся на

В качестве следствия теоремы 3.3.15 мы получаем, что в поле характеристики ни у одного элемента порядок не является кратным . Этот результат обобщается следующим образом.

Теорема 3.3.16. Пусть F — поле характеристики . Тогда для всех

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

Из теорем 3.3.15 и 3.3.16 вытекает

Следствие 3.3.17. Пусть — произвольный полином из один из его корней. Тогда — также корень полинома

Доказательство. Из легко следует, что

Если — неприводимый полином в — один из его корней, то — также корень полинома для любого натурального числа к, т.е. . Однако, поскольку степень полинома конечна, начиная с некоторого места, последовательность должна повторяться. Следующая теорема утверждает, что неприводимый полином из не имеет кратных корней ни в каком расширении поля.

Теорема 3.3.18. Пусть — неприводимый полином в степени , и пусть К — поле, содержащее . Если — корень полинома то все корни суть а,

Доказательство. Из замечаний, предшествующих теореме, мы видим, что суть все корни полинома .

Пусть — наименьшее натуральное число, с которого последовательность начинает повторяться, т.е. пусть Тогда а, — все различные корни полинома [Иначе из мы получаем , откуда противоречит минимальности ] Поэтому имеет по крайней мере корней, .

Для завершения доказательства пусть . Так как то — корень полинома Таким образом, принадлежит и по теореме 3.3.10 полином должен делить поскольку , мы имеем

Докажем теперь обращение теоремы 3.3.6.

Теорема 3.3.19. Для степени простого числа существует одно, и с точностью до изоморфизма ровно одно, конечное поле из q элементов. Эти элементы — корни полинома

Доказательство. Рассмотрим полином Тогда по теореме 3.3.9 существует поле расщепления К для полинома полином может быть представлен в виде произведения линейных сомножителей.

Пусть F — подмножество поля К, состоящее из всех корней полинома в К, т.е. состоит из всех элементов а таких, что Покажем, что F — искомое конечное поле.

Для этого нам нужно показать, что F содержит элементов и что оно — поле. По теореме [поскольку мы находимся в и производная полинома равна —1], и, следовательно, нет в К кратных корней. Поэтому в К имеется различных корней полинома и F содержит элементов. Чтобы показать, что F — поле, мы должны доказывать, что если то то же верно и для а Детали мы оставляем читателю. (Указание. Воспользуйтесь теоремой

Мы теперь в состоянии доказать следующий результат.

Теорема 3.3.20. Для любого в существует неприводимый полином степени .

Доказательство. Пусть F — конечное поле из элементов. Тогда по следствию 3.3.13 поле F изоморфно для некоторого неприводимого полинома Поэтому поле также имеет элементов, и степень равна .

Теперь ясно, что любой неприводимый полином степени в имеет корень в любом поле F из элементов. Это верно, потому что поле F изоморфно в котором имеет корень, а именно Поэтому имеет корень в

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

Теорема 3.3.21. Полином равен произведению всех неприводимых полиномов в степени которых делят г.

Доказательство. Пусть — неприводимый полином степени над и рассмотрим поле F, полученное присоединением к корня а полинома очевидно, F содержит элементов. В силу теоремы 3.3.10 мы знаем, что для любого полинома равенство справедливо, если и только если делится на Кроме того, по следствию 3.3.3 каждый элемент поля F — корень полинома в F; в частности, следовательно, делится на Однако то же верно и в случае потому что если и, применяя это соотношение раз, мы видим, что а — корень полинома

Для завершения доказательства покажем методом от противного, что если s не делит , то ни один неприводимый над полином степени s не делит Предположим, что и что Рассмотрим поле F, получающееся из присоединением к нему корня а полинома . Мы можем считать а примитивным корнем в поле т.е. является минимальным из натуральных чисел , таких, что Поскольку элемент а является также корнем полинома т.е. Пусть где q — остаток от деления на s. Тогда поскольку индукцией по к легко показать, что Если то полученное выше соотношение противоречит предположению о примитивности корня а.

Пример. Рассмотрим поле Галуа где и выразим в виде произведения неприводимых полиномов в (Заметим, что ) Ясно, что сомножитель с корнями а, (по теореме 3.3.18), т.е. (см. табл. 3.3.1 для проверки последнего равенства). Другие очевидные сомножители — полиномы

Возьмем теперь степень элемента а, которая еще не рассматривалась, а именно, Тогда другим сомножителем будет полином с корнями т.е. полином Сомножитель появляется потому, что последний полином имеет корень а значит, будет также иметь корень

Таблица 3.3.1 Три различных представления элементов поля

Затем рассмотрим и еще один сомножитель — полином . Наконец, последний сомножитель — это полином Сомножитель появляется, потому что последний полином имеет корень следовательно, он будет также иметь корень Аналогично сомножитель появляется, потому что — корень и Поэтому