Порядок элемента в поле

Порядок элемента в поле

Число элементов конечного поля

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

Теорема 4.15. Конечное поле F характеристики р содержит q = р п элементов, где п есть степень расширения F относительно простого подполя Р.

Доказательство. Пусть F : Р| = п. Это значит, что векторное пространство F над полем Р имеет базис из п элементов: <Ь1; b2, . Ьп>. Но тогда всякий элемент а е Р однозначно представим в виде линейной комбинации базисных элементов: а = а1Ъ1 + а2Ь2 + . + amb„, причем каждый коэффициент а,-, i = 1, 2, . п, может принимать р различных значений. Отсюда следует, что число таких линейных комбинаций равно q = р". Теорема доказана.

В силу доказанной теоремы поле Галуа обозначается GF(p n ) или GF(q). Корректность этого определения вытекает из того, что, как будет показано ниже, конечное поле однозначно с точностью до изоморфизма определяется числом его элементов q=p n .

*. Мультипликативная группа конечного поля

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

Теорема 4.16. Мультипликативная группа конечного поля циклическая.

Доказательство. Пусть Р — конечное поле и G = Р* — его мультипликативная группа. По теореме 1.25 она равна прямому произведению своих максимальных р-подгрупп по различным простым. Пусть S — одна из максимальных р-подгрупп группы G. Выберем в ней элемент максимального порядка. Пусть | а | = р а . Тогда для любого элемента s е S имеем sp“ = 1, откуда sP a -1 = 0. Следовательно, всякий элемент из S является корнем многочлена хр“ -1. Очевидно, а 0 , а, а 2 , . аР“ -1 — различные корни этого многочлена. Но многочлен степени р а имеет не более чем р а различных корней. Следовательно, перечисленными степенями элемента исчерпываются все корни многочлена х р“ -1. Отсюда следует, что группа циклическая: S — (а). Итак, группа G является прямым произведением максимальных р-подгрупп, каждая из которых циклическая. Следовательно, G является прямым произведением циклических подгрупп взаимно простых порядков. По теореме 1.24 группа циклическая. Теорема доказана.

Установим ряд интересных и важных свойств элементов конечного поля, которые приведут нас к одному утверждению в теории чисел.

Теорема 4.17. Элементы конечного поля Р = GF(q) являются корнями многочлена хч — х.

Доказательство. Порядок мультипликативной группы Р* данного поля Р равен q — 1, следовательно, для любого ее элемента g имеем = е, где е — единичный элемент поля. Отсюда

следует, что всякий элемент поля является корнем многочлена хЯ — х. Теорема доказана.

Теорема 4.18. Произведение всех ненулевых элементов конечного поля равно -е, где еединичный элемент поля.

Доказательство. Пусть дано конечное поле Р = GF(q). Тогда порядок мультипликативной группы поля равен |Р*| = q — 1.

Пусть Р*=а, а2. а^>. Многочлен Слг^- 1 -е)- П(* -а 😉 имеет

q — 1 различных корней, а его степень меньше q — 1. Следовательно, это нулевой многочлен. В частности, его свободный

член равен нулю: -е-(-1)‘? _1 ] _ [а( =0. Если характеристика р

данного поля нечетна, то число q — 1 -р п — 1 четно и (-1) a i = 0> откуда П а ; =

е — Если же характеристика

поля р = 2, то имеем е = -е, откуда снова получаем ]”[ а, = -е.

Следствие (теорема Вильсона). Если натуральное число р является простым, то (р — 1)! = -1 (modp).

Доказательство. Множество всех ненулевых элем ентов поля Р = Zp исчерпывается классами вычетов <1,2, . р-1>, и по теореме 4, 1-2-. -р-1 = -1, откуда (р — 1)! = —1, что равносильно сравнению (р — 1)! s -1 (modp). (Другое доказательство см. в работе [3].)

Читайте также:  Определение графика функции по точкам

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

Порядком (ненулевого) элемента конечного поля далее будем называть мультипликативный порядок рассматриваемого элемента.

Таким образом, для любого ненулевого элемента GF[q) справедливо равенство а° 1, где с — порядок элемента. При этом любой ненулевой элемент а порядка с поля GF(q) является корнем двучленах 0 -1 и уравнениях 0 -1 = 0.

В общем случае различные элементы поля GF(q) могут иметь различные порядки. Однако при этом очевидно, что максимально возможный порядок элемента поля GF(q) имеет значение q — 1. Очевидно также, что существование такого элемента означает, что все ненулевые элементы поля можно представить в виде степеней одного элемента порядка q — 1.

Предположим, что это не так. Тогда все множество элементов поля GF(q) образовано степенями некоторых двух элементов а и Ь порядков т и к соответственно [т h , h h — 1, и условие принадлежности элемента Ь множеству своих степеней нарушается. Равенство b = a h — 1 означает, что множество степеней элемента Ь, по сути, образовано степенями элемента а.

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

Элемент поля, степени которого образуют все ненулевые элементы поля, называется примитивным элементом.

Очевидно, что порядок примитивного элемента поля GF(q) всегда имеет значение q-1.

Забегая вперед, отметим, что примитивных элементов в общем случае может быть несколько. Однако к этому вопросу мы вернемся позже (см. подпараграф 1.6.1). Пока же обозначим то, что мы уже сейчас можем сказать о примитивных элементах поля на основе ранее установленных свойств поля.

В любом поле GF(q) существует как минимум один примитивный элемент, степени которого образуют все q — 1 ненулевых элементов поля. Так как порядок примитивного элемента GF всегда равен q- 1, то примитивный элемент этого поля всегда является корнем двучлена х9

1 -1 и уравнения:

Пример 1.4.4. Рассмотрим циклическую группу, образованную элементом 3 поля GF(5). Согласно правилам умножения элементов в поле GF(5), 3 1 = 3, З 2 =

= 3-3 = 4, З 3 = 3 2 -3 = 4-3 = 2, З 4 = 3 3 -3 = 2-3 = 1, З 5 = 3 4 -3 = 1-3 = 3, З 6 = 3 5 -3 = 3-3 = = 4, З 7 = 3 6 -3 = 4-3 = 2, и так далее. Таким образом, последовательность степеней будет повторяться, начиная с пятой степени. То есть порядок элемента 3 в данном случае равен четырем и все ненулевые элементы поля GF(5) могут быть представлены в виде степени элемента 3. Иными словами, в этом случае элемент 3 соответствует определению примитивного элемента. То же самое справедливо для элемента 2.

Следует понимать, что соответствие всех ненулевых элементов поля степеням примитивного элемента вовсе не означает равенство порядков всех элементов поля. Поскольку q — простое и, следовательно, нечетное число, то число q -1 всегда четно и, следовательно, имеет как минимум два простых делителя. В общем случае разложение числа q-1 соответствует разложению (1.2).

Читайте также:  Может быть белый цвет черным станет текст

Пусть число с — некоторый простой делитель числа q — 1. Тогда (q — 1 )lc = h и для элемента a h поля GF(q) справедливо: (a h ) c = a hc = а^

1 = 1, и элемент a h одновременно является корнем уравнения (1.28) и уравнения:

Таким образом, в поле GF[q), помимо примитивных элементов порядка q — 1, также должны существовать элементы, порядки которых являются делителями числа q-1.

Пример 1.4.5. Рассмотрим поле GF(5). Делителем числа q — 1 = 4 в этом случае является только простое число к = 2. При этом h = (q-‘)lk = 4/2 = 2. Примитивными элементами поля GF(5), как мы видели выше, являются элементы 2 и 3. Степень /7 = 2 примитивных элементов 2 и 3 равна элементу 4. Рассмотрим ряд степеней элемента 4: 4° = 1,4 1 = 4,4 2 = 1. Следовательно, порядок элемента 4 поля GF(5) равен двум.

Сказанное о примитивном элементе простого поля GF(q) справедливо также для примитивного элемента поля расширения. Поскольку число ненулевых элементов GF(Q) как расширения GF(q m ) поля GF(q) имеет значение Q — 1 = q m — 1, то порядок примитивного элемента поля GF(q m ) также должен иметь значение q m —1, а примитивный элемент поля GF(q m ) должен удовлетворять уравнению:

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

Уравнению (1.30) удовлетворяет не только примитивный, но и любой другой ненулевой элемент поля GF(q m ). К этому вопросу мы вернемся чуть позже в этой главе (см. подпараграф 1.6.3).

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

Отметим, что среди полиномов степени не выше присутствуют и полиномы нулевой степени, т.е. элементы простого поля , сложение и умножение которых, осуществляются по правилам . Это означает, что простое поле полностью содержится в расширенном , или, другими словами, является подполем. Для поля порядок его простого подполя называется характеристикой поля . Например, любое расширенное поле является полем характеристики 2, вследствие чего вычисление коэффициентов полиномов, рассматриваемых как элементы поля , осуществляется по модулю два. В частности, для любого ,, поскольку .

Мультипликативный порядок элементов поля. Примитивные элементы. Другой подход к построению расширения поля Галуа

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

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

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

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

Читайте также:  Функция подставить в экселе

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

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

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

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

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

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

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

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

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

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

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

Некоторые свойства расширенных конечных полей

Теорема 2.6.1. Среди всех элементов расширенного поля только для элементов основного подполя , т.е. для 0 и 1, выполняется соотношение

Доказательство: Справедливость указанного соотношения для нулевого элемента поля очевидна. Среди всех ненулевых элементов поля мультипликативный порядок, равный единице, имеет лишь 1, что и завершает доказательство теоремы.

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

Доказательство: Поскольку поле имеет характеристику, равную 2, то сомножитель в разложении бинома обращается в нуль. Следовательно

Данная теорема может быть обобщена на случай любого натурального и произвольного числа элементов :

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

Пусть . Тогда элементы поля вида

называются 2 — сопряженными с элементом .

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

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

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

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

Ссылка на основную публикацию
Подключение коллекторного двигателя постоянного тока
Колле́кторный электродви́гатель — электрическая машина, в которой датчиком положения ротора и переключателем тока в обмотках является одно и то же...
Перенос почты с одного хостинга на другой
Перенос почты со стороннего хостинга вам необходимо выполнить самостоятельно. Помощь со стороны технической поддержки, к сожалению, не предоставляется. Для переноса...
Перенос информации с самсунга на самсунг
У компании Samsung есть хорошая разработка, которая носит название Smart Switch. Благодаря ей вы можете узнать, как перенести данные с...
Подключение компьютер к компьютеру через кабель
Количество владельцев двух и более домашних компьютеров (ноутбуков) постоянно увеличивается. У каждого такого человека периодически возникает необходимость переноса определенных файлов...
Adblock detector