8.2. Мультипликативный порядок элементов поля. Примитивные элементы.

В любом поле , является ли оно простым или расширенным, определена операция–кратного умножения элемента. Естественно назвать такое произведение–ой степенью элемента, обозначив его как

.

Тогда

,

и для любого ненулевого

.

Следовательно, в конечных полях действуют те же самые правила обращения с целочисленными степенями элементов, что и в обычной арифметике.

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

,

мультипликативным порядкомэлемента. Очевидно, что только единичный элемент любого конечного поля обладает мультипликативным порядком, равным единице, т.е..

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

Теорема 8.2.1.Мультипликативный порядок любого ненулевого элементаполяделит, т.е. число ненулевых элементов поля.

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

Пример 8.2.2.В поле(см. пример 8.1.1) число ненулевых элементов поля является простым:, а, значит, делителями его могут быть только 1 и 7. Поскольку единственным элементом порядка 1 является единичный, то все остальные ненулевые элементы имеют максимальный мультипликативный порядок, равный 7.

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

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

Пример 8.2.3.Элементы 3 и 5 поля(см. пример 8.2.1) являются примитивными, тогда как остальные ненулевые элементы поля – не примитивны. Действительно,степеней элемента 3 различны:,,,,и. Для не примитивного элемента поля, например, 2 аналогичные вычисления дают следующий результат:,,,,и, и значит, возводя 2 в различныестепеней, можно получить лишь некоторые (но не все) ненулевые элементы поля.

Пример 8.2.4.В поле(см. пример 8.2.2) все ненулевые элементы поля за исключением единицы примитивны, поскольку число ненулевых элементов является простым и, следовательно, возможные значения мультипликативного порядка ограничены 1 и 7. Тогда возведение любого из этих элементов в степень от 0 до 6 позволяет получить все ненулевые элементы поля.

Рассмотренные примеры позволяют сделать следующее утверждение.

Утверждение 8.2.1. Если мультипликативный порядок элементаравен, то порядок элементаопределяется как

,

где – наибольший общий делитель.

Утверждение 8.2.2.В любом полесодержитсяпримитивных элементов, где– функция Эйлера, указывающая число целых чисел из диапазона от 1 до, взаимно простых с.

Расширенное поле, построенное как множество полиномов по модулю некоторого неприводимого полинома (см. пример 8.1.1), всегда содержит в качестве элемента поля полином . Если окажется, что– примитивный элемент, то соответствующий неприводимый полином называетсяпримитивным полиномом. Примитивные полиномы произвольной степениопределены над любым конечным полем. Они являются полезным инструментом для построения расширенных полей, поскольку позволяют реализовать очень простой вариант таблицы умножения элементов поля. Действительно, любые ненулевые элементыирасширенного полямогут быть выражены как некоторые–я и–я степени примитивного элемента:,. Тогдаи, значит, таблица умножения двух элементов поляипредставляет собой ни что иное, как все не нулевые степени примитивного элемента.

Таким образом, построение расширенного поля в виде степеней примитивного элемента предполагает следующий алгоритм действий. На первом этапе выбирается некоторый примитивный полином степенинад основным полем, которые содержатся в специальных таблицах:. Тогда–я степеньпо модулюопределится как. Предположение о примитивностипозволяет задатьв виде. Отсюда

.

Учитывая, что и подставляя его в последнее соотношение, получаем в явном виде выражение для–й степени. Последовательное возведение в степеньпозволяет, таким образом, определить все ненулевые элементы расширенного поля в виде линейной комбинации первыхстепеней:,, …,с коэффициентами из основного поля.

Пример 8.2.5.Полиномявляется примитивным над. Учитывая, что в поле, построенном по модулю,, и обозначая, получаем. Последовательное нахождение степеней примитивного элементапо ранее приведенному алгоритму задает все ненулевые элементы расширенного поля. Результаты проведенных таким образом вычислений приведены в таблице 8.2.

Таблица 8.2.

0=											1
1=									
2=							2
3=	3					=				+	1
4=							2	+	
5=	3	+	2			=	2	+		+	1
6=	3	+	2	+		=	2			+	1
7=	3			+		=					1

Поскольку иумножение этих элементов поля осуществляется как, что значительно экономичнее, чем это было реализовано в примере 8.1.1.

Пример 8.2.6.Построим полена основе примитивного полинома. Как и в примере 8.2.5, учитывая, что в полеи обозначая, получаем. Тогда последовательное возведение в степень примитивного элементадает все ненулевые элементы поля. Результаты вычислений представлены в таблице 8.3.