Подполя в gf(pm).
Можно теперь проинтерпретировать конструкцию теоремы 3, Л-2, РПЭК (если неприводимый над полем GF(p) многочлен степени n, то множество всех многочленов от x степеней с коэффициентами из поля GF(p), операции над которыми выполняются по модулю многочлена , образует поле порядка ), воспользовавшись общим подходом к построению расширений полей. Сначала присоединим к GF(p) корень неприводимого над GF(p) многочлена степени m и построим поле . Пусть теперь неприводимый над многочлен степени n. Образуем новое поле, присоединив к нему корень многочлена . Соображения, использованные в лекции 2, приводят к выводу, что это новое поле содержит элементов. Согласно теореме 1 мы построили поле . Таким образом, итерация конструкции теоремы 3 не дает никаких новых полей. Однако такой двухшаговый переход от поля GF(p) к позволяет доказать следующую полезную теорему.
Теорема 2. (i) Поле содержит подполе (изоморфное ) тогда и только тогда, когда s делит r.
(ii) Элемент принадлежит полю тогда и только тогда, когда . В любом поле из равенства следует, что элемент равняется 0 или 1.
Для доказательства воспользуемся результатом, который был получен в свое время2) при изучении теории делимости целых чисел. Сформулируем его в виде леммы.
Лемма. Если целые числа такие, что ; ; , то тогда и только тогда, когда .
Д о к а з а т е л ь с т в о теоремы 2 (i). Расширение поля содержит все корни многочлена , причем все корни этого многочлена различны. Если , то многочлен делится на многочлен , но последний сам по себе образует поле , то есть поле содержит подполе, изоморфное полю . Наоборот, пусть примитивный элемент поля . Тогда ; . Таким образом, и согласно лемме .
(ii) Первое утверждение вытекает непосредственно из теоремы Ферма (см. Л-2, РПЭК), а второе очевидно.
В качестве примера на Рис.1 показаны все подполя поля .
Сопряженные элементы и циклотомические классы
М6. Минимальные многочлены элементов и равны. В частности, в поле GF(2m) равны минимальные многочлены элементов и .
Д о к а з а т е л ь с т в о проведем конструктивным путем, используя конкретный пример. Пусть минимальный многочлен элемента , который принадлежит полю GF(24). В любом поле характеристики p выполняется известное равенство , соответственно которому , то есть элемент также является корнем многочлена . В силу свойства (М2) минимальный многочлен элемента должен делить многочлен . Но и потому после возведения в восьмую степень минимального многочлена элемента (если -корень, то корнями многочлена будут и , и и ) можно прийти к заключению, что корнем этого многочлена является и элемент , то есть минимальный многочлен элемента должен делить минимальный многочлен элемента . Значит, эти минимальные многочлены равны.
Рис.1. Подполя поля
Элементы поля, минимальные многочлены которых совпадают, называются сопряженными (по этой же причине мнимые числа i и i называют комплексно-сопряженными: над полем действительных чисел многочлен является минимальным для них обоих).
Таким образом, согласно (М6), если , то для поля характеристики 2 имеем
, ,
, …
Следовательно, элементы , являются корнями того же самого минимального многочлена (все эти элементы имеют тот же самый
минимальный многочлен). Аналогично, минимальным многочленом для элементов , , = (и ) является другой (тот же самый) минимальный многочлен и т.д. В результате можно сделать вывод, что степени элементов поля, которое рассматривается, можно объединить в непересекающиеся множества. Они получили специальное название циклотомические классы. Когда показатели степеней элементов поля принадлежат одному и тому же циклотомическому классу, минимальный многочлен для всех этих элементов является тем же самым.
В общем случае не двоичного поля GF(pm) циклотомический класс состоит из чисел
,
где наименьшее положительное число такое, что
).
Более строгое определение циклотомического класса можно представить в виде следствия следующей теоремы.
Теорема 3. Множество целых чисел по модулю относительно операции умножения на простое число p распадается на непересекающиеся подмножества. Эти подмножества называются циклотомическими классами по модулю .
Например, циклотомическими классами по модулю 15 (для p = 2) являются:
;
;
;
;
.
Наши обозначения выбраны так, что если наименьшее число в классе, то класс обозначается как . Индексы { } называются представителями классов по модулю .
Справедливость утверждаемого в теореме вытекает из того, что представители разных классов по модулю не сравнимы по этому модулю.
Введем для минимальных многочленов, которые отвечают циклотомическому классу , обозначение (минимальный многочлен элемента ).