Коды Рида-Соломона. Часть 2 — арифметика полей Галуа
Здравствуйте, друзья! В прошлый раз мы с вами начали говорить о том, как коды Рида-Соломона помогают обеспечивать необходимый уровень надежности хранения данных. Сегодня остановимся немного подробнее на арифметике полей Галуа, которая используется в расчётах.
Сначала краткий экскурс в прошлую часть. Мы выяснили — чтобы иметь возможность восстанавливать потерянные данные, необходимо сначала определенным образом сгенерировать «избыточные данные». Причем, с математической точки зрения, эта задача (кодирования) сводится к построению некоторой порождающей матрицы и выполнению операции умножения этой матрицы на вектор исходных данных. Процедура восстановления (декодирования), в свою очередь, заключается в обращении порождающей матрицы и умножения её на вектор сохранившихся данных. Схематически это можно изобразить следующим образом.
Ограничения арифметики рациональных чисел
Мы уже отмечали некоторые трудности, с которыми приходится сталкиваться при реализации процедур кодирования/декодирования на конкретных аппаратных платформах. Так, например, числа в памяти ЭВМ обычно представлены фиксированным количеством байтов. Как следствие, при умножении элементов порождающей матрицы, можно получить переполнение разрядов. Или при обращении порождающей матрицы в качестве ее элементов могут возникнуть рациональные числа, которые проблематично хранить с произвольной точностью. Поэтому, сегодня мы с вами поговорим о том, как можно реализовать данные процедуры, избегая вышеуказанных проблем. В этом нам поможет теория полей Галуа, о которой мы уже немного говорили в прошлой статье.
Сразу сделаю несколько замечаний. Во-первых, статья прежде всего рассчитана на инженерную аудиторию, поэтому я старался избегать строгих математических определений. Тем, кому хочется более формального введения в данную область, имеет смысл сразу обратиться к соответствующей литературе. Со своей стороны, могу порекомендовать книгу Эрнеста Борисовича Винберга «Курс алгебры». Во-вторых, непосредственно для реализации алгоритмов избыточного кодирования достаточно лишь базового понимания теории конечных полей. Можно просто считать, что заданы некоторые непротиворечивые таблицы умножения, деления, сложения, вычитания и все вычисления происходят с использованием этих таблиц. Это намек для тех, кому не очень хочется глубоко погружаться в данный раздел алгебры.
Поля и арифметические операции в конечных множествах
Прежде чем перейти непосредственно к обсуждению полей Галуа, давайте повторим еще раз, чего мы хотим достичь. Мы хотим иметь возможность умножать матрицы на вектора, обращать матрицы. А самое главное, мы хотим иметь дело только с целыми числами и не переживать за переполнение при выполнении операций умножения и сложения.
Также, во избежание путаницы, имеет смысл сразу разобраться с терминологией. Прежде всего, что такое поле с точки зрения общей алгебры? Как сообщает нам Википедия, «поле — множество, для элементов которого определены операции сложения, вычитания, умножения и деления (кроме деления на нуль), причём свойства этих операций близки к свойствам обычных числовых операций». Что такое поле Галуа? Поле Галуа — это произвольное поле, состоящие из конечного числа элементов. , — стандартное обозначение полей Галуа, где в скобках указывается количество элементов поля.
В современных ЭВМ для хранения чисел обычно используется фиксированное число бит. Нетрудно посчитать, что всего существует различных n-битовых чисел, от 0 и до . Другими словами, мы имеем некоторое конечное множество чисел. На этом множестве мы сейчас попытаемся непротиворечивым образом определить операции умножения, деления, сложения и вычитания. Причем так, чтобы результат любой операции также был -битовым числом! В этом случае говорят, что множество замкнуто относительно введенных операций.
Операция вычитания в системах конечных множеств обычно вводится через понятие нулевого и противоположного элементов. Нулевой элемент — это такой элемент, для которого справедливо равенство: , где – произвольный элемент множества. Элемент является противоположным для , если верно равенство . Обычно противоположный элемент обозначается как . Если мы хотим из вычесть , мы находим противоположный элемент и складываем его с . Соответственно, для того, чтобы иметь возможность вычитать произвольные элементы конечного множества, каждый элемент этого множества должен обладать противоположным.
Аналогичным образом обстоят дела и с операцией деления. Вводится понятие единичного и обратного элементов. Единичный элемент — это такой элемент, для которого верно равенство , где — произвольный элемент множества. Элемент (обозначается как ) называется обратным к , если . Как и при вычитании, если мы хотим разделить на ненулевой , мы должны найти обратный элемент и умножить его на . Для того, чтобы иметь возможность делить произвольные элементы, каждый элемент множества (за исключением нулевого) должен обладать обратным.
Построение полей Галуа GF(p)
Каким образом мы можем определить на конечном множестве чисел указанные арифметические операции, причём так, чтобы множество было замкнуто относительно них? Другими словами, мы хотим произвольное конечное множество элементов превратить в поле Галуа. Первое что приходит в голову, это воспользоваться модульной арифметикой. Тогда если наше множество содержит элементов, то результатом произведения чисел будет является число . Сумма чисел определяется как .
В качестве упражнения, давайте составим таблицы сложения и умножения для множества, состоящего из элементов . 
На нижних двух таблицах представлены противоположные и обратные значения для каждого элемента нашего множества. Вооружившись этими таблицами, мы можем выполнять все необходимые нам арифметические операции. Ура!
Построение полей Галуа
Кажется, что мы на верном пути к успеху. Единственное, что нас может пока не устраивать, так это размер нашего поля – 5. Понятно, что для упрощения программной реализации, имеет смысл работать с множествами, содержащими чисел. Тогда мы сможем оперировать полубайтами, байтами, словами и т.д.
На первый взгляд кажется, какая разница, — 5 или 256 элементов в множестве, берём результат операции умножения или сложения по соответствующему модулю и готово. Давайте снова попробуем составить таблицу умножения для множества, но на этот раз содержащего элемента — . Вот что получилось: ![Таблица умножения для <0,1,2,3>» width=»300″ /></p>
<p>Если пристально посмотреть на полученную таблицу, можно обнаружить в ней один серьезный недостаток. Обратите внимание на строчку для элемента 2. В этой строчке нет единичного элемента! Это означает, что мы не сможем делить другие элементы на 2, поскольку для него не существует обратного! Значит, необходимо производить построение таблиц сложения и умножения каким-либо другим способом. Модульная арифметика, к сожалению, больше не работает.</p>
<p>Итак, мы выяснили, что если множество содержит объекта, то модульная арифметика не позволяет задавать непротиворечивые операции умножения. На самом деле, подобные проблемы возникнут для любого множества, количество элементов которого не является простым числом. Но что ещё можно придумать?</p>
<h3>Сложение в GF(p^n)</h3>
<p>По сути дела, это обычное двоичное представление числа. Таким образом, любое число из нашего множества мы можем также рассматривать как вектор длины , элементы которого нули и единицы: </p>
<p>Введём операцию сложения двух любых чисел через сложение соответствующих векторов двоичного разложения. Причем сложение компонентов векторов мы будем вести <b>по модулю</b> 2 (в общем случае, если количество элементов , по модулю ). Таким образом, результирующий вектор также будет двоичным представлением некоторого числа и, как следствие, будет принадлежать нашему множеству (множество будет замкнуто относительно операции сложения). </p>
<p>Несложно заметить, что введенная нами операция сложения эквивалентна битовой операции «исключающее ИЛИ» (XOR). Что очень хорошо, поскольку современные процессоры могут выполнять данную операцию чрезвычайно быстро. Но это еще не все. Очевидно, что для произвольного числа . Это означает, что противоположным элементом к является сам . Таким образом, в поле сложение совпадает с вычитанием!</p>
<h3>Умножение в GF(p^n)</h3>
<p>Здесь коэффициенты многочлена берутся из двоичного разложения числа . При таком подходе, например, числу будет поставлен в соответствие многочлен .</p>
<p>Операцию умножения двух чисел мы можем определить через умножение многочленов, соответствующих данным числам: </p>
<p>Причем при перемножении все операции с коэффициентами многочленов выполняются по модулю 2.</p>
<p>Но теперь, очевидно, может возникнуть другая проблема. При перемножении двух многочленов степени , может получиться многочлен более высокой степени, который не будет соответствовать ни одному из чисел нашего множества. Это решается следующим образом. Выбирается неприводимый многочлен степени . Грубо говоря, это такой многочлен, который нельзя представить в виде произведения других многочленов, подробнее в статье. После это, используя алгоритм деления многочленов столбиком, который многие могут помнить еще по школьной программе, мы делим результат произведения на неприводимый многочлен. Еще раз напоминаю, что при делении столбиком, операции с коэффициентами многочленов также выполняются по модулю 2. В итоге, получаем многочлен степени, не выше чем , который мы и принимаем за результат произведения двух чисел. Вот пример выполнения умножения двух чисел над полем с использованием неприводимого многочлена . Данный многочлен используется в алгоритме шифрования AES/Rijndael.</p>
<p>Мы рассмотрели поле . Произвольные поля строятся аналогичным образом, только вместо двоичного представления числа используется -ичное и все вычисления проводятся по модулю .</p>
<h3>Изоморфизм полей и поля Галуа произвольного размера</h3>
<p>А что будет, если выбрать другой неприводимый многочлен? Можно даже поставить более общий вопрос. Предположим, мне вообще не нравятся все эти многочлены и деления столбиком, поэтому я лучше придумаю свою непротиворечивую таблицу умножения используя какой-нибудь другой принцип. Будет ли это чем то, принципиально новым? Ответ — нет. Все эти полученные поля будут изоморфны.</p>
<p>Переводя с «математического» языка, изоморфизм означает, что отличия только в обозначении элементов полей и одно можно свести к другому, выбрав соответствующее правило отображения.</p>
<p>Конечные множества элементов, которые мы рассматривали до сих пор, были двух типов. Первый тип множеств имел число элементов, равное некоторому простому числу . На таких множествах нам удалось задать таблицы умножения и сложения, используя лишь модульную арифметику. Ко второму типу относятся множества, имеющие , — простое, число элементов. На таких множествах возможно задать умножение/сложение используя схему с многочленами. Можно ли задать похожим образом умножение/сложение для множеств произвольного размера, скажем содержащих 6 элементов? Ответ — нет, это невозможно.</p>
<p>Собственно говоря, конечные поля и называются полями Галуа, потому, что он открыл их следующие важные свойства:</p>
<h2>Какое поле называется полем галуа</h2>
<p>В настоящем параграфе будет изучена несколько подробнее, чем в § 6.4, структура полей Галуа. Полученные результаты потребуются нам в следующем параграфе, посвященном кодам Боуза-Чоудхури — Хоквингема (БЧХ); они играют главенствующую роль во многих проводящихся в настоящее время исследованиях по технике алгебраического кодирования.</p>
<p>Начнем с изучения мультипликативного порядка различных ненулевых элементов поля Галуа состоящего из элементов. Так как ненулевые элементы поля, обозначенные, допустим, символами образуют абелеву группу по умножению в рассматриваемом поле, то из теоремы 6.3.2 следует, что каждый из этих элементов имеет мультипликативный порядок, на который делится число Поэтому при всех Отсюда следует, что каждый элемент является корнем многочлена [рассматриваемого здесь в качестве многочлена над Так как степень этого многочлена равна и известны ровно его различных корней, т. е. то получим</p>
<p>Например, в поле целых чисел по модулю 3 это равенство будет</p>
<p>которое, очевидно, удовлетворяется, если производить сложение и ум ножение целых чисел по модулю 3.</p>
<p>Выше было показано, что все ненулевые элементы поля, состоящего из элементов, имеют мультипликативный порядок, на который делится число Примитивным элементом поля из элементов называется элемент, у которого мультипликативный порядок точно равен Если можно найти некоторый примитивный элемент поля, допустим а, то последовательность содержит все ненулевые элементы поля, а мультипликативная группа ненулевых элементов поля является циклической. При этом ясно, что не представляет труда нахождение мультипликативного порядка любого элемента, являющегося степенью элемента а (см. задачу 6.26).</p>
<p>Теорема 6.6.1. Любое поле Галуа содержит примитивный элемент.</p>
<p>Доказательство. Пусть максимальный мультипликативный порядок ненулевых элементов поля равен Из теоремы 6.3.3. следует, что каждый ненулевой элемент имеет мультипликативный порядок, который является делителем и поэтому этот элемент является корнем Так как этот многочлен имеет корней, то имеем Поскольку согласно (6.6.1) каждый ненулевой элемент поля имеет мультипликативный порядок, на который делится число то что завершает доказательство.</p>
<p>Доказанная выше теорема в принципе полностью характеризует мультипликативную группу ненулевых элементов поля Галуа, однако она ничего не говорит о структуре аддитивной группы или о связи между умножением и сложением. Ниже эта связь будет найдена и показано, что все поля Галуа могут быть представлены как поля многочленов по модулю неприводимого многочлена. Прежде всего определим подполе некоторого поля как поле, элементы которого образуют подмножество элементов первоначального поля с операциями сложения и умножения, совпадающими с операциями первоначального поля. Если какое-либо поле имеет подполе то говорят, что является расширением</p>
<p>Теорема 6.6.2. Любое поле Галуа содержит единственное подполе, число элементов в котором простое.</p>
<p>Доказательство. Любое подполе должно содержать элементы поля 0 и 1. Оно должно также включать в себя и т. д. Обозначим эти получающиеся при сложении элементы через из теоремы 6.3.2 следует, что эти элементы, называемые целыми элементами поля, образуют циклическую подгруппу по операции сложения. Если эта подгруппа имеет элементов, то сложение этих элементов является сложением по модулю Согласно дистрибутивному закону умножение этих элементов также является умножением по модулю [т. е. Отсюда следует, что число простое, поскольку если бы было произведением двух целых чисел то для соответствующих им целых элементов поля удовлетворялось бы равенство Это невозможно, так как ненулевые элементы первоначального поля. Как было показано, целые по модулю простого числа элементы образуют поле, поэтому это поле как раз и является тем подполем, которое разыскивается.</p>
<p>Наконец, любое другое подполе должно содержать эти целые элементы поля, а аддитивная группа любого подполя должна содержать эти целые элементы как подгруппу. Поэтому число элементов в любом другом подполе делится на и потому не является простым.</p>
<p>Из этой теоремы непосредственно следует, что любое поле или подполе о простым числом элементов является при соответствующей нумерации элементов полем целых элементов по модулю простого числа. Характеристикой поля Галуа называется число элементов в определенном выше простом подполе.</p>
<p>Если многочлен над полем и если поле является расширением то говорят, что элемент а из является корнем многочлена когда т. е. когда</p>
<p>В качестве часто используемого примера укажем, что привычно находить комплексные корни многочленов над полем действительных чисел. Если является подполем поля Галуа то минимальный многочлен над элемента а, принадлежащего определяется как нормированный многочлен минимальной степени над у которого а является корнем. В дальнейшем во всех случаях, когда подполе явно не определено, мы будем иметь в виду подполе с простым числом элементов, фигурирующее в теореме 6.6.2.</p>
<p>Теорема 6.6.3. Для любого подполя поля Галуа каждому ненулевому элементу а, принадлежащему соответствует единственный минимальный многочлен над причем неприводимый. Более того, для любого многочлена над многочлен является делителем тогда и только тогда, когда а является корнем</p>
<p>Доказательство. Было уже показано, что а является корнем Так как можно рассматривать как многочлен над то отсюда следует существование таких многочленов над для которых а является корнем, и, следовательно, существует некоторый нормированный многочлен минимальной степени, обозначаемый для которого а является корнем. Если бы был приводимым, то он мог бы быть представлен в виде произведения двух нормированных многочленов меньшей степени над полем т. е. Отсюда следует, что и так как элементы, принадлежащие то один из них должен быть равным 0, что противоречит предположению о том, что имеет минимальную степень. Поэтому неприводим. Тогда для любого над</p>
<p>где многочлен над Е, степень которого меньше степени/а Так как то Поэтому тогда и только тогда, когда Но поскольку степень меньше, чем степень то получаем, что в свою очередь, тогда и</p>
<p>только тогда, когда является нулевым многочленом. Поэтому тогда и только тогда, когда является делителем Наконец, если является нормированным многочленом той же самой степени, что и то равенство выполняется лишь при что доказывает единственность</p>
<p>В доказанной выше теореме утверждение о неприводимости многочлена означает, что над полем не существует многочленов меньшей степени, произведение которых было бы равно Если интерпретировать как многочлен над то а является очевидным делителем</p>
<p>Следствие. Пусть подполе поля Галуа и пусть различные минимальные многочлены над соответствующие ненулевым элементам [т. е. последовательность из которой исключены одинаковые многочлены]. Тогда</p>
<p>Заметим, что соотношение (6.6.1) описывает разложение на неприводимые многочлены над на неприводимые многочлены над</p>
<p>Доказательство. Так как ненулевые элементы из являются корнями то каждый минимальный многочлен является делителем Поскольку минимальные многочлены неприводимы (над полем то произведение также является делителем Наконец, все ненулевые элементы являются корнями многочлена</p>
<p>Следовательно, указанное выше произведение имеет степень, не меньшую и (6.6.3) выполняется.</p>
<p>Теорема 6.6.4. Пусть а — примитивный элемент поля Галуа характеристики и пусть степень минимального многочлена над элемента а равна Тогда число элементов в поле Галуа равно и каждый элемент поля может быть представлен в виде</p>
<p>при некотором наборе целых элементов поля</p>
<p>Доказательство. Так как а является корнем то имеем или</p>
<p>Поскольку каждый из коэффициентов является целым элементом</p>
<p>поля, то нетрудно видеть, что элемент может быть представлен в виде (6.6.4). Умножая (6.6.5) на а, получаем</p>
<p>В силу того, что можно представить в виде (6.6.4), также можно представить в таком виде; последовательно умножая (6.6.6) на более высокие степени а, убеждаемся, что все степени а могут быть представлены в виде (6.6.4). Поэтому каждый элемент может быть представлен в виде (6.6.4). Теперь допустим, что имеются два различных множества целых элементов поля, входящих в (6.6.4), например которые соответствуют одному и тому же элементу из Тогда</p>
<p>Отсюда следует, что а является корнем многочлена</p>
<p>что невозможно, поскольку степень этого многочлена меньше Поэтому каждый из наборов соответствует различным элементам поля и так как существует всего таких наборов целых элементов поля, то.</p>
<p>Эта теорема имеет ряд интересных следствий. Во-первых, поскольку характеристикой всякого поля Галуа является некоторое простое число то число элементов во всяком поле Галуа должно представляться в виде где некоторое простое число, некоторое целое число. Далее, если в соотношении (6.6.4) заменить а на не определенную то можно убедиться, что множество элементов поля может рассматриваться как множество многочленов над степени, не большей умножением по модулю Другими словами, это поле после введения в нем новых обозначений элементов будет совпадать с полем многочленов над по модулю (т. е. будет иметь то же самое множество элементов и те же самые правила сложения и умножения). Два таких поля, отличающиеся лишь обозначениями элементов, называются изоморфными; из приведенных рассуждений следует, что всякое поле с элементами изоморфно некоторому полю многочленов над по модулю некоторого неприводимого многочлена степени Наконец, согласно (6.6.3) из единственности разложения многочлена над на неприводимые множители следует, что всякое поле с элементами имеет одно и то же множество минимальных многочленов. Поэтому в любом поле с элементами можно выбрать в качестве а корень фиксированного многочлена использованного в теореме (6.6.4), и представить все элементы поля в виде (6.6.4). Таким образом, доказана следующая теорема.</p>
<p>Теорема 6.6.5. Все поля Галуа с элементами изоморфны данному полю многочленов над по модулю неприводимого многочлена степени.</p>
<h2>Поля Галуа</h2>
<p>В настоящем разделе буква $ p_<> $ обозначает простое число.</p>
<h3>Структура конечного поля</h3>
<p>Существование конечных полей, т.е. полей, состоящих из конечного числа элементов установлено в пункте ☞ ПОЛЕ.</p>
<p><strong>Пример.</strong> Множество $ \mathbb Z_ </p>
<p>$ классов вычетов по простому модулю $ p_<> $ образует поле относительно операций сложения и умножения.</p>
<p>Рассмотрим теперь конечные поля самого общего вида. Любое такое поле $ \mathbb F_<> $ должно содержать нейтральный элементы относительно сложения и умножения: $ \mathfrak o $ — нулевой и $ \mathfrak e $ — единичный. Начнем последовательно складывать единичные элементы $$ \mathfrak a_1= \mathfrak e,\ \mathfrak a_2=\mathfrak e+\mathfrak e,\ \mathfrak a_3=\mathfrak e+\mathfrak e+\mathfrak e,\dots $$ Поскольку, по предположению, поле содержит лишь конечное число элементов, то элементы последовательности $ \<\mathfrak a_j\>_ <j\in \mathbb N>$ должны повторяться. Если $ \mathfrak a_k= \mathfrak a_ <\ell>$ при $ k<\ell $, то $$ \mathfrak a_<\ell-k>= \mathfrak a_<\ell>-\mathfrak a_k = \mathfrak o \ . $$ Таким образом, в рассматриваемой последовательности обязательно встретятся нулевые элементы.</p>
<p><strong>Теорема 1.</strong> <em>Пусть первый нулевой элемент последовательности</em> $ \ <\mathfrak a_j\>$ <em>имеет номер</em> $ M_<> $: $$ \mathfrak a_M=\mathfrak o, \mathfrak a_j \ne \mathfrak o \quad npu \quad j\in \ <1,\dots,M-1\>. $$ <em>Число</em> $ M_<> $ — <em>простое. Все элементы</em> $ \mathfrak a_1,\dots,\mathfrak a_ <M-1>$ <em>различны</em>.</p>
<p><strong>Доказательство.</strong> Если $ M_<> $ — составное: $ M=M_1M_2 $ при $ M_1<M $ и $ M_2<M $, то $$ \mathfrak o=\mathfrak a_M=\mathfrak a_<M_1>\cdot \mathfrak a_ <M_2>\ . $$ Оба элемента $ \mathfrak a_ <M_1>$ и $ \mathfrak a_ <M_2>$ по предположению, ненулевые, а их произведение — нулевой элемент. Но это противоречит свойству поля. Оставшееся утверждение теоремы докажите самостоятельно. ♦</p>
<p>Простое число $ M=p_<> $ из предыдущей теоремы называется <strong>характеристикой конечного поля</strong>.</p>
<p><strong>Теорема 2.</strong> <em>Порядок (число элементов) любого конечного поля равен некоторой степени его характеристики</em>: $$ \operatorname <Card>(\mathbb F) = p^m \quad \mbox < при >\quad p \mbox < - простом и >\quad m \in \mathbb N \ . $$</p>
<p><strong>Доказательство.</strong> В предыдущей теореме было доказано, что конечное поле $ \mathbb F $ характеристики $ p_<> $ содержит $ p_<> $ различных элементов: $$ \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_ <p-1>\quad npu \quad \mathfrak a_j= \underbrace<\mathfrak e + \dots+ \mathfrak e>_ <j>\ . $$ Это множество обладает всеми свойствами поля и изоморфно полю $ \mathbb Z_p $. Изоморфизм устанавливается соответствием $ \mathfrak a_j \mapsto \overline j $. Действительно, по предположению $ \mathfrak a_p= \mathfrak o $, но тогда $$ \mathfrak a_<p+1>= \mathfrak a_1, \mathfrak a_<p+2>= \mathfrak a_2, \dots , \mathfrak a_<p+j>= \mathfrak a_j, \dots , $$ а следовательно, $ \mathfrak a_j+ \mathfrak a_k=\mathfrak a_<j+k>=\mathfrak a_< j+k \pmod
<p>> $. Таким образом $ \mathfrak a_j+ \mathfrak a_k \mapsto \overline <j +k>$, т.е. соответствие сохраняет результат сложения. Результат умножения также сохраняется, поскольку на основании свойств поля (в частности, дистрибутивности умножения относительно сложения), следует $$ \mathfrak a_j \cdot \mathfrak a_k=\mathfrak a_ <jk>= \mathfrak a_<jk \pmod
<p>> \ , $$ т.е. $ \mathfrak a_j \cdot \mathfrak a_k \mapsto \overline <jk>$.</p>
<p>Установленный изоморфизм позволяет утверждать, что любой элемент $ \mathfrak a_j \ne \mathfrak o $ имеет обратный среди чисел того же множества: $ \mathfrak a_<j>^ <-1>= \mathfrak a_ <s>$, где $ s_<> $ — число, обратное $ j_<> $ относительно умножения по модулю $ p_<> $.</p>
<p>Если в поле $ \mathbb F $ нет других элементов, то $ \mathbb F = \< \mathfrak a_j \>_<j=0>^ <p-1>$ и теорема доказана: $ \operatorname <Card>(\mathbb F) = p $. Предположим, что существует $ \mathfrak A \in \mathbb F $ и $ \mathfrak A \not\in \< \mathfrak a_j \>_<j=0>^ <p-1>$. Тогда множество $$ \<\mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \>_<j,k=0>^ <p-1>$$ определяет $ p^2 $ <em>различных</em> элементов поля $ \mathbb F $. Действительно, если $$ \mathfrak a_<j_<_1>>+ \mathfrak a_<k_<_1>> \cdot \mathfrak A = \mathfrak a_<j_<_2>>+ \mathfrak a_<k_<_2>> \cdot \mathfrak A ,\ \mbox < то >\quad \mathfrak a_<j_<_1>>- \mathfrak a_<j_<_2>>=(\mathfrak a_<k_<_2>>-\mathfrak a_<k_<_1>>) \mathfrak A \ . $$ Если $ \mathfrak a_<k_<_2>>-\mathfrak a_<k_<_1>> \ne \mathfrak o $, то, по доказанному в предыдущем абзаце, существует обратный к элементу $ \mathfrak a_<k_<_2>>-\mathfrak a_<k_<_1>> $ и этот элемент находится в том же множестве $ \< \mathfrak a_j \>_<j=1>^ <p-1>$. Тогда из последнего равенства следует, что $$ \mathfrak A=(\mathfrak a_<k_<_2>>-\mathfrak a_<k_<_1>>)^ <-1>(\mathfrak a_<j_<_1>>- \mathfrak a_<j_<_2>>) \quad \Rightarrow \quad \mathfrak A \in \< \mathfrak a_j \>_<j=0>^ <p-1>\ , $$ что противоречит предположению. Если же $ \mathfrak a_<k_<_2>>- \mathfrak a_<k_<_1>> = \mathfrak o $, то тогда и $ \mathfrak a_<j_<_1>>-\mathfrak a_<j_<_2>> = \mathfrak o $.</p>
<p>Если в поле $ \mathbb F $ нет других элементов, то $ \mathbb F =\< \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \>_<j,k=0>^ <p-1>$ и $ \operatorname <Card>(\mathbb F) = p^2 $. В противном случае, существует элемент $ \mathfrak B_<> $, не входящий в это подмножество, и мы рассмотрим множество $$ \ < \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A + \mathfrak a_<\ell>\cdot \mathfrak B \>_<j,k,\ell=0>^ <p-1>\ , $$ которое определяет $ p^3 $ <em>различных</em> элементов поля $ \mathbb F $. Дальнейший ход доказательства аналогичен предыдущим рассуждениям. Поскольку, по предположению, число элементов поля конечно, то процесс должен завершиться за конечное число шагов и если последний шаг имеет номер $ m_<> $, то получим утверждение теоремы. ♦</p>
<p><strong>Пример.</strong> Рассмотрим поле, состоящее из $ 4_<> $-х элементов. Два из них — это нейтральные элементы $ \mathfrak o $ и $ \mathfrak e $. Два оставшихся обозначим $ \mathfrak a $ и $ \mathfrak b $. Попробуем выписать для этих элементов таблицы сложения и умножения, руководствуясь только аксиомами поля. Начнем со сложения. На основании того, что характеристика поля равна $ p=2 $ получаем $$ \mathfrak e + \mathfrak e = \mathfrak o \ . $$ Чему может равняться сумма $ \mathfrak a+ \mathfrak e $? Если $ \mathfrak a+ \mathfrak e= \mathfrak o $, то, прибавляя к обеим частям равенства $ \mathfrak e $, на основании предыдущего равенства, получаем $ \mathfrak a = \mathfrak e $, что противоречит предположению, что $ \mathfrak a $ отличен от $ \mathfrak o $ и $ \mathfrak e $. Аналогичным приемом показываем невозможность равенства $ \mathfrak a+ \mathfrak e= \mathfrak e $ — оно приводит к $ \mathfrak a = \mathfrak o $. Пусть теперь $ \mathfrak a+ \mathfrak e= \mathfrak a $. На основании аксиомы поля 3 , для элемента $ \mathfrak a $ должен существовать противоположный относительно сложения; мы пока не знаем, чему он равен, но знаем, что он существует. Обозначим его $ x_<> $, тогда $ \mathfrak a +x = \mathfrak o $. Прибавим этот элемент к обеим частям предполагаемого равенства $ \mathfrak a+ \mathfrak e= \mathfrak a $, получим $ \mathfrak e= \mathfrak o $, что незаконно.</p>
<p>Остается лишь один возможный вариант: $ \mathfrak a+ \mathfrak e= \mathfrak b $. Отсюда просто получается и второе равенство: $ \mathfrak b+ \mathfrak e= \mathfrak a $. Итак, таблица сложения (с учетом обязательной для поля коммутативности этой операции) частично заполнена: $$ \begin<array> <r|rrrr>\mathbb <+>& \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak e & \mathfrak e & \mathfrak o & \mathfrak b & \mathfrak a \\ \mathfrak a & \mathfrak a & \mathfrak b & & \\ \mathfrak b & \mathfrak b & \mathfrak a & & \end <array>$$ Пытаемся заполнить оставшиеся места. Чему может быть равна сумма $ \mathfrak a+ \mathfrak a $? Равенство $ \mathfrak a+ \mathfrak a = \mathfrak a $ невозможно, поскольку из него следовало бы, что $ \mathfrak a = \mathfrak o $. Если $ \mathfrak a+ \mathfrak a = \mathfrak b $, то прибавляя к обеим частям равенства $ \mathfrak e $ получим, с использованием уже заполненных частей таблицы, что $ \mathfrak a+ \mathfrak b = \mathfrak a $, что снова приводит к неверному равенству $ \mathfrak b = \mathfrak o $. Пусть $ \mathfrak a+ \mathfrak a = \mathfrak e $. Для доказательства противоречивости этого равенства приходится использовать операцию умножения. По аксиоме поля 8 , имеем: для элемента $ \mathfrak a $ должен существовать обратный относительно умножения; мы пока не знаем, чему он равен, но знаем, что он существует. Обозначим его $ y_<> $, тогда $ \mathfrak a \cdot y = \mathfrak e $. Умножим его на равенство $ \mathfrak a+ \mathfrak a = \mathfrak e $, с использованием аксиомы 4 приходим к $ \mathfrak e+ \mathfrak e = y $, откуда $ y= \mathfrak o $, что невозможно. Остался единственный вариант: $ \mathfrak a+ \mathfrak a = \mathfrak o $. Теми же самыми рассуждениями доказываем, что и $ \mathfrak b+ \mathfrak b = \mathfrak o $.</p>
<p>Осталось найти $ \mathfrak a+ \mathfrak b $. Эта сумма не может быть равна ни $ \mathfrak a $, ни $ \mathfrak b $, поскольку, по предположению, $ \mathfrak a \ne \mathfrak b $. Равенство $ \mathfrak a+ \mathfrak b = \mathfrak o $ также невозможно, поскольку, прибавляя к обеим его частям $ \mathfrak a $, и используя результат предыдущего абзаца, приходим к тому же противоречию: $ \mathfrak a = \mathfrak b $. Таким образом, единственный оставшийся вариант: $ \mathfrak a+ \mathfrak b = \mathfrak e $. Окончательно таблица сложения должна иметь вид: $$ \begin<array> <r|rrrr>\mathbb <+>& \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak e & \mathfrak e & \mathfrak o & \mathfrak b & \mathfrak a \\ \mathfrak a & \mathfrak a & \mathfrak b & \mathfrak o & \mathfrak e \\ \mathfrak b & \mathfrak b & \mathfrak a & \mathfrak e & \mathfrak o \end <array>$$ Теперь займемся умножением. Начальную часть таблицы заполнить легко: $$ \begin<array> <r|rrrr>\mathbb <\times>& \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o \\ \mathfrak e & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak a & \mathfrak o & \mathfrak a & & \\ \mathfrak b & \mathfrak o & \mathfrak b & & \end <array>$$ Чему равно произведение $ \mathfrak a \cdot \mathfrak a $? Вариант $ \mathfrak a \cdot \mathfrak a = \mathfrak o $ отпадает, поскольку из него (домножением на обратный относительно умножения) следует $ \mathfrak a = \mathfrak o $. Заметим, что на том же основании, $$ \mathfrak b \cdot \mathfrak b \ne \mathfrak o \ . $$ Вариант $ \mathfrak a \cdot \mathfrak a = \mathfrak a $ влечет за собой $ \mathfrak a = \mathfrak e $, что также невозможно. Возможно ли, чтобы $ \mathfrak a \cdot \mathfrak a = \mathfrak e $, т.е. чтобы элемент $ \mathfrak a $ был обратен самому себе? С помощью таблицы сложения получим тогда цепочку следствий: $$ \mathfrak a \cdot \mathfrak a = \mathfrak e \quad \Rightarrow \quad \mathfrak a \cdot \mathfrak a + \mathfrak e = \mathfrak o \quad \Rightarrow \quad \mathfrak a \cdot \mathfrak a + \mathfrak a + \mathfrak a + \mathfrak e = \mathfrak o \quad \Rightarrow \quad (\mathfrak a + \mathfrak e)(\mathfrak a + \mathfrak e)= \mathfrak o \quad \Rightarrow \quad \mathfrak b \cdot \mathfrak b = \mathfrak o ; $$ последнее противоречит предыдущему неравенству. Итак, произведение $ \mathfrak a \cdot \mathfrak a $ может быть равно только $ \mathfrak b $. Аналогично доказывается, что $ \mathfrak b \cdot \mathfrak b $ может быть равно только $ \mathfrak a $.</p>
<p>Наконец, $$ \mathfrak a \cdot \mathfrak b = \mathfrak a \cdot (\mathfrak a+\mathfrak e) = \mathfrak a \cdot \mathfrak a + \mathfrak a = \mathfrak b + \mathfrak a = \mathfrak e \ . $$ Окончательно: $$ \begin<array> <r|rrrr>\mathbb <\times>& \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o \\ \mathfrak e & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak a & \mathfrak o & \mathfrak a & \mathfrak b & \mathfrak e \\ \mathfrak b & \mathfrak o & \mathfrak b & \mathfrak e & \mathfrak a \end <array>$$ ♦</p>
<p>Итак, цепочкой рассуждений мы пришли к выводу: если существует конечное поле из $ 4_<> $-х элементов, то в нем операции сложения и умножения должны производиться по единственно возможным сценариям, которые описываются полученными таблицами. Однако, остался открытым вопрос:</p>
<p>Нет ли противоречий в этих построенных таблицах?</p>
<p>В самом деле, возможно, что существует не найденная нами цепочка действий, которая приведет к противоречию с каким-то результатом из полученных таблиц. Ответ на этот вопрос оказывается отрицательным: противоречий мы не получим.</p>
<p><strong>Пример.</strong> Рассмотрим множество, состоящее из квадратных матрицы второго порядка</p>
<p>$$ \mathfrak o= \left( \begin<array> <cc>0 & 0 \\ 0 & 0 \end <array>\right),\ \mathfrak e= \left( \begin<array> <cc>1 & 0 \\ 0 & 1 \end <array>\right),\ \mathfrak a= \left( \begin<array> <cc>1 & 1 \\ 1 & 0 \end <array>\right),\ \mathfrak b= \left( \begin<array> <cc>0 & 1 \\ 1 & 1 \end <array>\right). $$ В этом множестве операцию сложения определим как операцию сложения матриц по модулю $ 2_<> $: $$ \left(\begin<array> <ll>a_<11>& a_ <12>\\ a_<21>&a_ <22>\end <array>\right)+ \left(\begin<array> <ll>b_<11>& b_ <12>\\ b_<21>&b_ <22>\end <array>\right)= \left(\begin<array> <ll>a_<11>+b_ <11>\pmod <2>& a_<12>+b_ <12>\pmod <2>\\ a_<21>+b_ <21>\pmod <2>& a_<22>+b_ <22>\pmod <2>\end <array>\right) $$ а операцию умножения — как операцию умножения матриц, но тоже по модулю $ 2_<> $, т.е.: $$ \left(\begin<array> <ll>a_<11>& a_ <12>\\ a_<21>&a_ <22>\end <array>\right)\times \left(\begin<array> <ll>b_<11>& b_ <12>\\ b_<21>&b_ <22>\end <array>\right) = \left(\begin<array> <ll>a_<11>b_ <11>+a_<12>b_ <21>\pmod <2>& a_<11>b_ <12>+a_<12>b_ <22>\pmod <2>\\ a_<21>b_ <11>+a_<22>b_ <21>\pmod <2>& a_<21>b_ <12>+a_<22>b_ <22>\pmod <2>\end <array>\right) \ . $$ Можно проверить, что таблицы действий с элементами этого множества совпадают с таблицами, приведенными выше. ♦</p>
<p>Пример конечного поля порядка $ p^ <m>$ будет приведен ☟ НИЖЕ. Любое такое поле называется <strong>полем Галуа</strong> и обозначается 1) $ \mathbf<GF>(p^m) $.</p>
<h3>Обобщенная теорема Ферма</h3>
<p><strong>Теорема.</strong> <em>Любой элемент</em> $ \mathfrak a \in \mathbf<GF>(p^m) $ <em>удовлетворяет равенству</em>$$ \mathfrak a^ <p^m>— \mathfrak a = \mathfrak o \ . $$</p>
<p><strong>Доказательство</strong> аналогично доказательству малой теоремы Ферма. Обозначим для краткости $ q=p^m $, и рассмотрим все ненулевые элементы поля $$ \mathfrak a_1,\dots, \mathfrak a_ <q-1>\ . $$ Если $ \mathfrak a \ne \mathfrak o $, то домножим его на все эти элементы: $$ \mathfrak a \mathfrak a_1,\dots, \mathfrak a \mathfrak a_ <q-1>\ . $$ Получились снова элементы поля. Они все отличны от $ \mathfrak o $ (поскольку в поле не существует делителей нуля) и все различны: $$ \mathfrak a \mathfrak a_j = \mathfrak a \mathfrak a_k \quad \Rightarrow \quad \mathfrak a (\mathfrak a_j — \mathfrak a_k)= \mathfrak o \quad \Rightarrow \quad \mathfrak a = \mathfrak o \quad \mbox < или >\quad \mathfrak a_j = \mathfrak a_k \ . $$ Следовательно множество $ \< \mathfrak a \mathfrak a_j \>_<j=1>^ <q-1>$ совпадает со множеством $ \< \mathfrak a_k \>_<k=1>^ <q-1>$, но тогда произведения элементов этих множеств одинаковы: $$ \prod_<j=1>^ <q-1>(\mathfrak a \mathfrak a_j) = \prod_<j=1>^ <q-1>\mathfrak a_j \quad \Rightarrow \quad a^ <q-1>\prod_<j=1>^ <q-1>\mathfrak a_j = \prod_<j=1>^ <q-1>\mathfrak a_j \ . $$ Произведение ненулевых элементов поля отлично от $ \mathfrak o $, следовательно $$ \mathfrak a^<q-1>= \mathfrak e \ ; $$ это равенство справедливо для любого ненулевого элемента поля. Умножив его на $ \mathfrak a $, получим равенство из условия теоремы, которому будет удовлетворять и $ \mathfrak a = \mathfrak o $. ♦</p>
<p><strong>Теорема.</strong> <em>Любой элемент</em> $ \mathfrak a \in \mathbf<GF>(p^m) $ <em>удовлетворяет равенству</em></p>
<p>Будем называть выражение вида $$ \mathfrak x^m + A_1 \mathfrak x^ <m-1>+ \dots + A_ <m>= \mathfrak o $$ при $ \ < A_1,\dots,A_m \>\subset \ < \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_<p-1>\> $ <strong>алгебраическим уравнением</strong> в $ \mathbf<GF>(p^m) $ степени $ m_<> $ относительно неизвестной $ \mathfrak x_<> $.</p>
<p><strong>Доказательство</strong>. При доказательстве теоремы 2 из предыдущего пункта было показано, что в любом поле $ \mathbb P $ найдутся $ m_<> $ элементов $ \mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m $ таких, что любой элемент поля можно выразить в виде их линейной комбинации с коэффициентами из множества $ \ < \mathfrak a_<j>\>_<j=0>^ <p-1>$. Выразим в виде таких линейных комбинаций элементы $ \mathfrak a, \mathfrak a \mathfrak A_1, \mathfrak a \mathfrak A_2,\dots, \mathfrak a \mathfrak A_m $: $$ \begin<array> <lcl>\mathfrak a &=& A_ <11>+A_ <12>\mathfrak A_2+\dots+ A_ <1m>\mathfrak A_m, \\ \mathfrak a \mathfrak A_2 &=& A_ <21>+A_ <22>\mathfrak A_2+\dots+ A_ <2m>\mathfrak A_m, \\ \dots & & \dots \\ \mathfrak a \mathfrak A_m &=& A_ <m1>+A_ <m2>\mathfrak A_2+\dots+ A_ <mm>\mathfrak A_m, \end <array>\qquad npu \quad \ < A_<jk>\>_<j,k=1>^m \subset \ < \mathfrak a_<j>\>_<j=0>^ <p-1>\ . $$ Перепишем эти уравнения: $$ \begin<array> <cccccc>(A_<11>— \mathfrak a) & +A_ <12>\mathfrak A_2 & +\dots & + A_ <1m>\mathfrak A_m &=& \mathfrak o, \\ A_ <21>& +(A_<22>— \mathfrak a) \mathfrak A_2 &+\dots & + A_ <2m>\mathfrak A_m &=& \mathfrak o, \\ \dots & & & & & \dots \\ A_ <m1>& + A_ <m2>\mathfrak A_2 & +\dots+ & (A_<mm>— \mathfrak a) \mathfrak A_m &=& \mathfrak o. \end <array>$$ Эта система уравнений, рассматриваемая относительно элементов поля $ \mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m $ является линейной и однородной.</p>
<p>Поскольку эта однородная система имеет нетривиальное решение ( $ \mathfrak A_1=\mathfrak e\ne \mathfrak o $), ее определитель должнен быть равен нулевому элементу поля: $$ \left|\begin<array> <cccc>A_<11>— \mathfrak a & A_ <12>& \dots & A_ <1m>\\ A_ <21>& A_<22>— \mathfrak a& \dots & A_ <2m>\\ \dots & & & \dots \\ A_ <m1>& A_<m2>& \dots & A_<mm>— \mathfrak a \end <array>\right|= \mathfrak o \ . $$ Определитель в левой части является полиномом от $ \mathfrak a $ степени $ m_<> $ с коэффициентами, которые полиномиально же зависят от величин $ \ < A_<jk>\>_<j,k=1>^m $, т.е., в конечном итоге, от величин $ \ < \mathfrak a_<j>\>_<j=0>^ <p-1>$. ♦</p>
<p>Резюмируем: элемент $ \mathfrak a $ поля $ \mathbf<GF>(p^m) $ должен удовлетворять одновременно двум алгебраическим уравнениям в этом поле: $ \mathfrak x^<p^m>— \mathfrak x = \mathfrak o $ и некоторому уравнению $ \mathfrak x^m + A_1 \mathfrak x^ <m-1>+ \dots + A_ <m>= \mathfrak o $ степени $ m_<> $. Если бы мы имели дело с обычными алгебраическими уравнениями одной переменной с целыми коэффициентами, то мы могли бы сделать заключение о существовании зависимости между коэффициентами этих уравнений в виде некоторого алгебраического равенства (см. ☞ РЕЗУЛЬТАНТ ). В случае же конечного поля, можно вывести более глубокое заключение: второй полином оказывается делителем первого. Осталось только ввести операцию деления полиномов в конечном поле, к чему мы и приступаем.</p>
<h3>Пример конечного поля</h3>
<p>Полином $ F_<>(x) $ с целыми коэффициентами называется <strong>неприводимым по модулю p</strong> если его нельзя представить в виде $$ F(x)\equiv F_1(x)F_2(x)+ p G(x) \ , $$ где $ F_1, F_2,G $ — полиномы с целыми коэффициентами и $ \deg F_1 < \deg F, \deg F_2< \deg F $. В противном случае будем говорить, что полином $ F_<>(x) $ <strong>приводим по модулю p</strong>; в этом случае будем также говорить, что $ F_<>(x) $ делится на $ F_j(x) $ по модулю $ p_<> $, или что $ F_j(x) $ является делителем $ F_<>(x) $ по модулю $ p_<> $.</p>
<p>Очевидно, что если полином $ F(x) \in \mathbb Z[x] $ приводим в $ \mathbb Z_<> $, то он приводим по любому модулю $ p_<> $.</p>
<p><strong>Пример.</strong> Приводим ли полином $ 2\,x^2+2\,x+1 $ по модулю $ 5_<> $?</p>
<p><strong>Решение.</strong> Этот полином неприводим в $ \mathbb Z_<> $. Тем не менее по модулю $ 5_<> $ он раскладывается на линейные множители, один из которых угадывается подстановкой $ x_<>=1 $: $$ 2\,x^2+2\,x+1\equiv (x-1)(2\,x+4)+5 \equiv (x-1)(2\,x+4) \pmod 5 \equiv $$ $$ \equiv (x-1)(2\,x-1) \pmod 5 \equiv (x+4)(2\,x+4) \pmod 5 \equiv \dots $$ ♦</p>
<p><strong>Пример.</strong> Приводим ли полином $ 2\,x^2+2\,x-1 $ по модулю $ 5_<> $?</p>
<p><strong>Решение.</strong> Рассмотрим всевозможные комбинации потенциально возможных линейных множителей с коэффициентами из множества $ \ <-2,-1,0,1,2\>$: $$ 2\,x\pm 1,\ 2\,x\pm 2,\ x\pm 2,\ x\pm 1 \ . $$ Ни одна пара при перемножении не дает требуемый полином.</p>
<p><strong>Ответ.</strong> Нет.</p>
<p>Рассмотрим полином $ f_<>(x) $ степени $ n_<>\ge 1 $ с целыми коэффициентами и нормализованный (т.е. со старшим коэффициентом равным $ 1_<> $): $$ f(x)=x^n+a_1x^<n-1>+\dots+a_n \in \mathbb Z[x] \ . $$ Доказать, что частное и остаток от деления произвольного полинома $ g_<> (x)\in \mathbb Z[x] $ на $ f_<>(x) $ будут полиномами с целыми коэффициентами.</p>
<p><strong>Подсказка</strong>: см. доказательство теоремы ☞ ЗДЕСЬ.</p>
<p>Полиномы $ \ <F_1(x),F_2(x)\>\subset \mathbb Z[x] $ называются <strong>сравнимыми по двойному модулю</strong> $ p, f(x) $ если их разность может быть представлена в виде $$ F_1(x)-F_2(x) \equiv p\cdot G(x) + f(x) H(x) \quad npu \quad \<G(x),H(x) \>\subset \mathbb Z[x] \ . $$ Иными словами, остаток от деления $ F_1(x)-F_2(x) $ на $ f_<>(x) $ представляет собой полином, все коэффициенты которого кратны $ p_<> $: $$ \left( F_1(x)-F_2(x) \pmod <f(x)>\right) \pmod </p>
<p>\equiv 0 \ ; $$ здесь знак $ \equiv_<> $ обозначает тождественное равенство. В [1] для этого понятия используется обозначение $$ F_1(x)\equiv F_2(x) \quad (\operatorname <modd>\ p,f(x)) \ , $$ на мой взгяд, очень наглядное. Однако ни в каком другом источнике я его не встречал.</p>
<p><strong>Пример.</strong> Найти все значения параметра $ \alpha \in \mathbb Z $, при которых полиномы</p>
<p>$$ F_1(x)=7\,x^3+4\,x^2-x-3 \quad u \quad F_2(x)=3\,x^3-5\,x^2+\alpha\, x+7 $$ будут сравнимы по модулю $ 5,\, x^2+x+2 $.</p>
<p><strong>Решение.</strong> Делим $ F_1(x)-F_2(x) $ на $ x^2+x+2 $: $$ F_1(x)-F_2(x) \equiv (4\,x+5)(x^2+x+2)+[(-14-\alpha)\,x-20] \ . $$ Остаток от деления равен $ (-14-\alpha)\,x-20 $, по модулю $ 5_<> $ он сравним с $ (1-\alpha)\, x $. Коэффициент при $ x_<> $ делится на $ 5_<> $ только при условии</p>
<p><strong>Ответ.</strong> $ \alpha \equiv 1 \pmod 5 $.</p>
<p>Будем использовать обозначение $$ F(x)= F_1(x) \quad (\operatorname <modd>\ p,f(x)) $$ в том же смысле, что в разделе ☞ МОДУЛЯРНАЯ АРИФМЕТИКА использовалось обозначение $ x = A \pmod <M>$, т.е. полиному $ F_<>(x) $ присваивается значение остатка от деления $ F_1(x) $ на $ f_<>(x) $, в котором дополнительно производится усечение каждого коэффициента до его остатка от деления на $ p_<> $.</p>
<p><strong>Пример.</strong> Для</p>
<p>$$ F_1(x)=5\,x^4-x^2+x-4,\ f(x)= x^3+2\,x^2+3\,x-6 $$ и $ p=7 $ имеем $$ F_1(x)\equiv (5\,x-10)f(x) +4\,x^2+61\,x-64 \quad \Rightarrow \quad F(x)=4\,x^2+5\,x+6 \equiv F_1(x) \quad (\operatorname <modd>\ 7,f(x)) \ . $$</p>
<p><strong>Теорема.</strong> <em>Пусть</em> $ f_<>(x) $ — <em>нормализованный неприводимый по модулю</em> $ p_<> $ <em>полином степени</em> $ m\ge 1 $. <em>Множество полиномов</em> </p>
<p>$$ \mathbb P_ <p,f>= \< F (x)=A_0+A_1x+\dots+A_<m-1>x^ <m-1>\ \mid \ \<A_0,A_1,\dots,A_<m-1>\> \subset \ <0,1,\dots,p-1 \>\> \ , $$ <em>рассматриваемое относительно операции сложения по модулю</em> $ p_<> $: $$ F_1(x)+F_2(x) \pmod </p>
<p>$$ <em>и операции умножения по двойному модулю</em> $ p, f(x) $: $$ F_1(x) F_2(x) \quad (\operatorname <modd>\ p,f(x)) $$ <em>образует поле Галуа</em> $ \mathbf<GF>(p^m) $.</p>
<p><strong>Доказательство.</strong> Все элементы множества $ \mathbb P_ <p,f>$ различны, поскольку каждый определяется набором своих коэффициентов $ (A_0,A_1,\dots,A_<m-1>) $ однозначно. Каждый из коэффициентов, независимо от других, может принимать $ p_<> $ различных значений, следовательно $ \operatorname <Card>( \mathbb P_ <p,f>) = p^m $.</p>
<p>Введенные во множестве $ \mathbb P_ <p,f>$ операции удовлетворяют аксиомам 1 — 8 поля; сложность вызовет лишь проверка аксиомы 8 о существовании полинома, обратного произвольному полиному $ F(x) \in \mathbb P_<p,f>, F(x) \not\equiv 0 $ относительно умножения по двойному модулю $ p,f(x) $. Требуется удостовериться, что существует полином $ U(x) \in \mathbb P_ <p,f>$ такой, что $$ U(x)F(x) \quad (\operatorname <modd>\ p,f(x)) \equiv 1 \ . $$</p>
<p>Если $ F_<>(x) $ тождественно равен константе $ F(x)\equiv A_0 $, то искомый полином $ U(x) $ тоже будет константой: $ U(x)\equiv U_0 $, где $ U_0A_0 \equiv 1 \pmod </p>
<p>$. Последнее сравнение имеет решение для любого $ A_0\in \ <1,\dots,p-1\>$, это решение будет единственны в том же множестве, и оно называется мультипликативным обратным числу $ A_0 $ по модулю $ p_<> $. Соответствующую теорию и сопутствующие алгоритмы нахождения см. ☞ ЗДЕСЬ; сугубо же для теоретических манипуляций нам достаточно будет его представления посредством малой теоремы Ферма: $$ A_0^<-1>= A^ <p-2>\pmod </p>
<p>\ . $$</p>
<p>Предположим теперь, что $ F(x) \not\equiv const $: $$ F(x) = A_0+A_1x+\dots+A_<\ell>x^ <\ell>\quad npu \quad A_ <\ell>\ne 0, \ell > 0 \ . $$</p>
<p>Разделим полином $ f_<>(x) $ на $ F(x) $: $$f(x)\equiv q_1(x)F(x)+r_1(x) , $$ здесь $ \deg q_1 = m-\ell, \deg r_1 < \ell $. Поскольку коэффициенты делимого и делителя целочислены, то коэффициенты частного $ q_1(x) $ и остатка $ r_1(x) $ будут рациональными числами; при этом знаменатели дробей могут быть только степенями числа $ A_ <\ell>$: $ \< 1,A_<\ell>,\dots, A_<\ell>^ <m-\ell+1>\> $. Заменим каждое рациональное число вида $$ \frac<B><A_<\ell>^K> $$ на $$ B A_<\ell>^ <p-K-1>\pmod </p>
<p>; $$ на основании малой теоремы Ферма, числа $ A_<\ell>^K $ и $ A_<\ell>^ <p-K-1>$ являются мультипликативными обратными относительно умножения по модулю $ p_<> $: $$A_<\ell>^<p-K-1>\cdot A_<\ell>^K \equiv 1 \pmod </p>
<p>\ . $$ Произведя все подобные замены в последнем полиномиальном тождестве, получим его целочисленный вариант $$f(x)\equiv Q_1(x)F(x)+R_1(x) , $$ но справедливый теперь по модулю $ p_<> $. Может ли полином $ R_1(x) $ оказаться тождественно равным $ 0_<> $ ? — Нет, поскольку при выполнении этого предположения, мы пришли бы к противоречию с тем фактом, что $ f_<> $, по предположению, является неприводимым полиномом по модулю $ p_<> $. Итак, $ R_1(x) $ не равен тождественно $ 0_<> $. Пусть он тождественно равен ненулевой константе $ R_1(x) \equiv C_0 $ при $ C_0\in \ <1,\dots,p-1\>$. Домножим тождество $$f(x)\equiv Q_1(x)F(x)+ C_0 $$ на мультипликативное обратное числу $ C_0 $ по модулю $ p_<> $, представив его, например, в виде $ C_0^ <p-2>\pmod </p>
<p>$. Получим $$ C_0^ <p-2>f(x) — C_0^<p-2>Q_1(x)F(x) \equiv 1 \pmod </p>
<p>\ . $$ Из последнего тождества тогда следует, что в качестве полинома $ U(x) $, удовлетворяющего $$ U(x)F(x) \quad (\operatorname <modd>\ p,f(x)) \equiv 1 \ , $$ можно взять $ [- C_0^<p-2>Q_1(x)] \pmod </p>
<p>$.</p>
<p>Идем далее. Предположим, что полином $ R_1(x) $ не является константой: $ \deg R_1>0 $. Разделим целочисленный полином $ F_<>(x) $ на целочисленный полином $ R_1(x) $: $$ F(x) \equiv q_2(x) R_1(x) + r_2(x) , \quad \deg r_2<\deg R_1 . $$ Коэффициенты частного $ q_2(x) $ и остатка $ r_2(x) $ будут рациональными числами; при этом знаменатели дробей могут быть только степенями старшего коэффициента полинома $ R_1(x) $. Повторяем процедуру избавления от знаменателей, использованную в предыдущем абзаце. Приходим к целочисленному тождеству $$ F(x)\equiv Q_2(x) R_1(x) + R_2(x) \ , $$ справедливому по модулю $ p_<> $. Если полином $ R_2(x) $ тождественно равен константе: $ R_2(x) \equiv D_0 $, то эта константа не должна быть нулем. В противном случае 3) $$ F(x)\equiv Q_2(x) R_1(x) \quad \Rightarrow \quad f(x)\equiv Q_1(x)F(x)+R_1(x) \equiv R_1(x) (Q_1(x)Q_2(x)+1) \ , $$ откуда вытекает приводимость полинома $ f_<>(x) $ по модулю $ p_<> $. Домножаем тождество $$ F(x)\equiv Q_2(x) R_1(x) + D_0 $$ на мультипликативное обратное числу $ D_0 $ по модулю $ p_<> $, представив его, например, в виде $ D_0^ <p-2>\pmod </p>
<p>$. Получим $$ D_0^ <p-2>F(x) — D_0^<p-2>Q_2(x)R_1(x) \equiv 1 \pmod </p>
<p>\ . $$ Подставим в это тождество представление для $ R_1(x) $ из его определения в предыдущем абзаце: $$ R_1(x) \equiv f(x)- Q_1(x)F(x), $$ приходим к тождеству $$D_0^ <p-2>(Q_1(x)Q_2(x)+1)F(x)-D_0^<p-2>Q_2(x)f(x) \equiv 1 . $$ Из него следует, что в качестве полинома $ U(x) $, удовлетворяющего $$ U(x)F(x) \quad (\operatorname <modd>\ p,f(x)) \equiv 1 \ , $$ можно взять $ D_0^ <p-2>(Q_1(x)Q_2(x)+1) \pmod </p>
<p>$.</p>
<p>Наконец, если полином $ R_2(x) $ не является константой: $ \deg R_2>0 $, то разделим целочисленный полином $ R_1(x) $ на целочисленный полином $ R_2(x) $: $$ R_1(x) \equiv q_3(x) R_2(x) + r_3(x) , \quad \deg r_3<\deg R_2 . $$ И повторяем рассуждения предыдущих абзацев. Рано или поздно процедура последовательного деления остатков должна закончиться, поскольку на каждом этапе происходит понижение степеней остатков. Пусть последний ненулевой остаток появляется на $ k_<> $-м шаге: $$R_<k-2>(x)\equiv Q_k(x) R_<k-1>(x)+ R_k $$ и $ R_k \not\equiv 0 \pmod </p>
<p>$. Умножив тождество на $ R_k^ <p-2>$ приведем его к виду $$1\equiv R_k^ <p-2>R_<k-2>(x)- R_k^ <p-2>Q_k(x) R_<k-1>(x) \ . $$ Далее возвращаемся назад в алгоритме последовательного деления. Из предпоследнего шага можно выразить $ R_<k-1>(x) $ через $ R_ <k-2>(x) $ и $ R_ <k-3>(x) $, подставив их выражения в последнее тождество, получим $$1\equiv R_k^<p-2>[1+Q_k(x)Q_<k-1>(x)] R_<k-2>(x)- R_k^ <p-2>Q_k(x) R_<k-3>(x) \ . $$ Возвращаемся еще на один шаг назад, выражаем правую часть последнего тождества через предшествующие остатки, и т.д. В конце концов, придем к представлению $$1 \equiv V(x)f(x)+U(x)F(x) \ . $$ Но оно эквивалентно искомому $$ U(x)F(x) \quad (\operatorname <modd>\ p,f(x)) \equiv 1 \ . $$ ♦</p>
<p>Практическое нахождение элемента, обратного в поле Галуа заданному, возможно разными способами. Все они, прямо или опосредовано, завязаны на полиномиальное тождество, известное под названием тождества Безу: это тождество имеет вид $$ v(x)f(x)+u(x)g(x)\equiv 1 \ . $$ При фиксированных полиномах $ f_<>(x) $ и $ g_<>(x) $ его выполнимость (хотя бы при одной паре полиномов $ u(x) $ и $ v(x) $) имеет место тогда и только тогда, когда $ f_<>(x) $ и $ g_<>(x) $ взаимно просты: $ \operatorname<HOD>(f,g) \equiv 1 $. Способы решения этого тождества в бесконечных полях посредством вычисления континуанты изложены в ☞ ПУНКТЕ; менее практичен, но более нагляден способ, основанный на представлении результанта полиномов $ f_<>(x) $ и $ g_<>(x) $ в виде подходящего определителя, составленного из коэффициентов этих полиномов: см. ☞ ЗДЕСЬ. Можно воспользоваться любым из этих способов для получения промежуточного результата в задаче обращения элемента в поле Галуа: для полиномов $ f_<>(x) $ и $ F_<>(x) $ с целочисленными коэффициентами, сначала получить представления полиномов $ v(x) $ и $ u(x) $ с коэффициентами <em>рациональными</em>, а затем избавиться от знаменателей дробей переходом к обратным по модулю $ p_<> $. Проиллюстрируем эту идею на примере.</p>
<p><strong>Пример.</strong> В поле $ \mathbf<GF>(7^5) $, порожденном полиномов $ f(x)=x^5+3\,x+1 $, найти элемент обратный $ 2\,x^4+3\,x^3+4\,x+1 $.</p>
<p><strong>Решение.</strong> Тождество Безу $$ v(x)f(x)+u(x)F(x)\equiv 1 \ . $$ будет иметь место при 4) $$ u(x)=-\frac<1561><650>-\frac<33><1300>x-\frac<22><325>x^2+\frac<307><1300>x^3-\frac<1023><1300>x^4, \quad v(x)\equiv \dots $$ Далее, решаем сравнения $$ 650\,z_1 \equiv 1,\ 1300 \,z_2 \equiv 1,\ 325 \, z_3 \equiv 1 \pmod <7>$$ получаем мультипликативные обратные к знаменателям $ z_1=6,z_2=3,z_3=5 \pmod <7>$. Избавляемся от знаменателей в коэффициентах полинома $ u_<>(x) $: $$U(x)=-1561 \cdot 6-33\cdot 3\,x -22\cdot 5\,x^2+307\cdot 3\,x^3-1023 \cdot 3\,x^4 \equiv_ <7>\dots $$</p>
<p><strong>Ответ.</strong> $ (2\,x^4+3\,x^3+4\,x+1)^ <-1>\quad (\operatorname <modd>\ 7,x^5+3\,x+1) = 4\,x^4+4\,x^3+2\,x^2+6\,x $.</p>
<p><strong>Пример.</strong> Построить поле $ \mathbf<GF>(4) $.</p>
<p><strong>Решение.</strong> Здесь $ p=2 $ и $ m_<>=2 $. Полином $ f(x)=x^2+x+1 $ является неприводимым по модулю $ 2_<> $. Согласно теореме, множество из четырех полиномов $ \ <0,1,x,x+1\>$ с операцией сложения по модулю $ 2_<> $ и операцией умножения по двойному модулю $ 2, x^2+x+1 $ образует поле. Результаты операций, собранные в таблицы $$ \begin<array> <c|cccc>\mathbb <+>& 0 & 1 & x & x+1 \\ \hline 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1 \\ x+1 & x+1 & x & 1 & 0 \end <array>\qquad \qquad \begin<array> <c|cccc>\mathbb <\times>& 0 & 1 & x & x+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1 \\ x+1 & 0 & x+1 & 1 & x \end <array>$$ полностью соответствуют приведенным в начале раздела, где выводились правила действий в произвольном поле $ \mathbf<GF>(4) $. Иными словами, существует изоморфизм между произвольным полем $ \mathbf<GF>(4) $ (например полем из четырех матриц, построенным в конце ☞ ПУНКТА ) и полем из полиномов, построенным в настоящем примере. ♦</p>
<p><strong>Теорема.</strong> <em>Конечные поля одинакового порядка изоморфны, т.е. между элементами этих полей можно установить такое взаимно-однозначное соответствие, которое сохраняет результаты сложения и умножения элементов.</em></p>
<p>Доказательства этой теоремы, приведенные в литературе, оказались трудны для моего понимания, поэтому я просто привожу проверку этого утверждения на примере ☞ ЗДЕСЬ.</p>
<h3>Полиномы, неприводимые по модулю</h3>
<p><strong>Теорема 1.</strong> <em>Любой неприводимый по модулю</em> $ p_<> $ <em>полином степени</em> $ n_<> $ <em>является делителем полинома</em> $ x^<p^n>— x $ (<em>по модулю</em> $ p_<> $).</p>
<p><strong>Доказательство</strong>. В предыдущем пункте было доказано, что если $ f_<>(x) $ неприводимый по модулю $ p_<> $ полином степени $ n_<> $, то множество $ \mathbb P_ <p,f>$ полиномов степеней $ < n $ с коэффициентами из $ \ <0,1,\dots,p-1\>$ образует поле Галуа $ \mathbf <GF>(p^n) $ относительно введенных операций сложения по модулю $ p_<> $ и умножения по двойному модулю $ p,f(x) $. Но тогда любой полином $ F(x) \in \mathbb P_ <p,f>$ должен удовлетворять обобщенной теореме Ферма: $$ \left[F(x)\right]^ <p^n>— F(x) \equiv 0 \quad (\operatorname <modd>\ p,f(x)) \ . $$ В частности, это должно быть справедливо и для $ F(x) \equiv x $. Тогда полином $$ x^<p^n>-x $$ должен делиться на полином $ f_<> (x) $ по модулю $ p_<> $. ♦</p>
<p>Таким образом, чтобы найти все неприводимые по модулю $ p_<> $ полиномы степени $ n_<> $ следует разложить полином $ x^<p^n>— x $ на неприводимые по модулю $ p_<> $ множители. При этом часть множителей может иметь степень $ < n_<> $. Однако, существование для любых $ p_<> $ и $ n_<> $ неприводимых по модулю $ p_<> $ полиномов степени $ n_<> $ еще требует доказательства.</p>
<p><strong>Теорема 2.</strong> <em>Если элемент</em> $ \mathfrak a \in \mathbf <GF>(p^m) $ <em>удовлетворяет неприводимому уравнению степени</em> $ n_<> $, <em>то равенство</em> $ \mathfrak a^ <p^m>— \mathfrak a = \mathfrak o $ <em>возможно тогда и только тогда, когда</em> $ m_<> $ <em>делится на</em> $ n_<> $.</p>
<p><strong>Доказательство</strong> ☞ ЗДЕСЬ.</p>
<p><strong>Теорема 3.</strong> <em>Полином</em> $ x^<p^m>— x $ <em>разлагается по модулю</em> $ p_<> $ <em>на неприводимые полиномы, степени которых равны или</em> $ m_<> $ <em>или делителям</em> $ m_<> $.</p>
<p>Непосредственным следствием теоремы 2 является</p>
<p><strong>Теорема 4.</strong> <em>Обозначим через 6) </em> $ \xi_p (k) $ <em>число неприводимых по модулю</em> $ p_<> $ <em>полиномов степени</em> $ k_<> $. <em>Имеет место равенство</em></p>
<p>$$ p^m=\sum_ <k>k \xi_p (k) \ ; $$ <em>здесь суммирование производится по всем индексам</em> $ k_<> $ <em>, являющимися делителями числа</em> $ m_<> $.</p>
<p>Определить $ \xi_p (m) $ для случая простого $ m_<> $. Установить для этого случая асимптотику $ \xi_p (m)/p^m $ при $ m \to \infty $.</p>
<p>Если в каноническом разложении числа $ m_<> $ на множители содержатся только различные простые числа, то имеет место равенство:</p>
<p>$$ \xi_p (m) =\frac<1> <m>\left(p^m- \sum_ <k_1>p^<m/k_<_1>>+\sum_<k_<_1>,k_<_2>> p^<m/(k_<_1>k_<_2>)>- \sum_<k_<_1>,k_<_2>,k_<_3>> p^<m/(k_<_1>k_<_2>k_<_3>)> + \dots \right) \ , $$ где $ k_1,k_2,k_3,\dots $ пробегают всевозможные делители числа $ m_<> $.</p>
<p><strong>Пример.</strong> Определить $ \xi_p (30) $.</p>
<p><strong>Решение.</strong> Поскольку $ 30=2\cdot 3 \cdot 5 $, то имеем: $$ \xi_p (30) = \frac<1> <30>\left(p^<30>-p^<15>-p^<10>-p^6+p^5+p^3+p^2-p \right) \ . $$ Так, $ \xi_2 (30)= 35790267,\ \xi_3 (30) =6863037256208 $. ♦</p>
<p>В поле Галуа <strong>первообразным корнем степени n из единицы</strong> называется элемент $ \mathfrak a $, который удовлетворяет условиям $$ \mathfrak a^n=\mathfrak e \ , \mathfrak a^k \ne \mathfrak e \quad npu \quad k\in \ <1,2,\dots,n-1\>\ . $$ Будем также говорить, что $ \mathfrak a $ <strong>принадлежит показателю n</strong> или, что $ \mathfrak a $ <strong>имеет порядок n</strong>.</p>
<p><strong>Теорема 5.</strong> <em>В поле Галуа</em> $ \mathbf <GF>(p^m) $ <em>существуют первообразные корни степени</em> $ p^m-1 $ <em>из единицы.</em></p>
<p><strong>Доказательство</strong> (и критерий, часто позволяющий быстро отыскать такие корни) ☞ ЗДЕСЬ.</p>
<p>В поле $ \mathbf <GF>(p^m) $ первообразный корень степени $ p^m-1 $ из единицы называется <strong>примитивным элементом поля</strong>.</p>
<p>Количество примитивных элементов поля $ \mathbf <GF>(p^m) $ равно $ \phi(p^m-1) $, где $ \phi $ — функция Эйлера.</p>
<p>В любом поле Галуа группа относительно умножения — циклическая, иными словами: все <em>ненулевые</em> элементы поля $ \mathbf <GF>(p^m) $ находятся во множестве $ \ < \mathfrak A^0,\mathfrak A^1,\dots,\mathfrak A^<p^m-1>\> $ при выборе в качестве $ \mathfrak A $ произвольного примитивного элемента.</p>
<p><strong>Пример 1.</strong> Пусть $ p=3, m=2 $. Выбрав в качестве неприводимого по модулю $ 3_<> $ полинома 7) </p>
<p>$$ f(x)=x^2-x-1 \, ,$$ получим, что элементами поля $ \mathbf <GF>(3^2) $ должны быть полиномы степени не выше $ 1_<> $ с коэффициентами из множества $ \ <-1,0,1\>$. Возьмем в качестве примитивного элемента поля полином тождественно равный 8) $ x_<> $. Получим, последовательным возведением его в степень: $$ x^0\equiv 1,\ x^1\equiv x,\ x^2 \equiv x+1 \quad (\operatorname <modd>\ 3,x^2-x-1 ) , \ x^3\equiv x\cdot x^2 \equiv x^2+x\equiv 2\,x+1 \equiv — x+1 , \ $$ т.е. каждый раз умножаем результат предыдущего шага на $ x_<> $ и в правой части производим формальную замену $ x^2 \to x+1 $; $$ \begin<array> <l>x^4\equiv -x^2+x \equiv -x-1+x\equiv -1,\\ x^5 \equiv -x,\\ x^6 \equiv -x^2 \equiv -x-1,\\ x^7 \equiv -x^2-x\equiv -x-1-x \equiv x-1, \\ x^8 \equiv x^2-x \equiv 1 \ . \end <array>$$ Цикл завершен. ♦</p>
<p><strong>Теорема 6.</strong> <em>Полином</em> $ x^<p^m>— x $ <em>содержит неприводимые по модулю</em> $ p_<> $ <em>сомножители степени</em> $ m_<> $.</p>
<p><strong>Доказательство.</strong> Если бы первообразный корень $ \mathfrak a $ степени $ p^m -1 $ из единицы удовлетворял бы уравнению степени $ n<m $, то, в силу теоремы 1, он удовлетворял бы также и уравнению $ \mathfrak a^ <p^n>— \mathfrak e = \mathfrak o $, что, ввиду неравенства $ p^n-1 < p^m-1 $ невозможно. ♦</p>
<p><strong>Пример 2.</strong> Разложить полином $ x^<16>-x $ на неприводимые по модулю $ 2_<> $ множители.</p>
<p><strong>Решение.</strong> Воспользуемся результатом из пункта УРАВНЕНИЕ ДЕЛЕНИЯ КРУГА. $$ x^<16>-x \equiv x \left(x^<15>-1 \right) \equiv x\, X_1(x)X_3(x)X_5(x)X_<15>(x) \equiv $$ $$ \equiv x(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^8-x^7+x^5-x^4+x^3-x+1) \ . $$ Здесь полиномы $ X_j(x) $ — неприводимы в $ \mathbb Z_<> $. Чтобы найти разложение на неприводимые по модулю $ 2_<> $ полиномы, воспользуемся сначала результатом теоремы 3 для определения количества этих неприводимых полиномов. Имеем: $$ \begin<array> <rcrrr>16 & = & 4 \xi (4) & + 2\xi (2) & + \xi (1), \\ 4 & = & & 2\xi (2) & + \xi (1), \\ 2 & = & & & \xi (1), \end <array>$$ откуда: $ \xi (1)=2, \xi (2)=1, \xi (4)=3 $. Таким образом, получаем что по модулю $ 2_<> $ имеется (в-точности) $ 2_<> $ неприводимых линейных полинома, оба уже наблюдаются в разложении: $$ x \quad \mbox < и >\quad x-1 \equiv x+1 \pmod <2>\ ; $$ Неприводимый полином $ 2_<> $-й степени единствен — и он также уже содержится в разложении: $$ x^2+x+1 \ . $$ Что касается неприводимых полиномов $ 4_<> $-й степени, то их должно быть $ 3_<> $. Один из них уже содержится в разложении: $$ x^4+x^3+x^2+x+1 \ ; $$ два остальных содержатся в разложении $ x^8-x^7+x^5-x^4+x^3-x+1 $ на множители по модулю $ 2_<> $: $$ x^8-x^7+x^5-x^4+x^3-x+1 \equiv (x^4+x^3+1)(x^4+x+1) \pmod <2>\ . $$ ♦</p>
<p><strong>Пример 3.</strong> Найти все неприводимые по модулю $ 2_<> $ полиномы $ 3_<> $-й степени.</p>
<p><strong>Решение.</strong> Для получения этих полиномов — в соответствии с теоремой 3 — надо разложить на множители полином $ x^<2^3>-x $. Имеем $$ x^<8>-x\equiv x(x-1)(x^6+x^5+x^4+x^3+x^2+x+1) \equiv x(x-1)(x^3+x^2+1)(x^3+x+1) \pmod 2 \ . $$ Оба полученных полинома $ 3_<> $-й степени неприводимы по модулю $ 2_<> $, поскольку по теореме 3 получаем $$ \begin<array> <rcrr>4 & = & 3\xi (3) & + \xi (1), \\ 2 & = & & \xi (1), \end <array>$$ откуда $ \xi (3)=2 $. ♦</p>
<p><strong>Пример 4.</strong> Разложить полином $ x^<9>-x $ на неприводимые по модулю $ 3_<> $ множители.</p>
<p><strong>Решение.</strong> Здесь $ p=3,m=2 $ и из теоремы имеем $$ \begin<array> <rcrr>9 & = & 2\xi (2) & + \xi (1), \\ 3 & = & & \xi (1), \end <array>$$ т.е. $ \xi (1)=3, \xi (2)=3 $. Разложим полином $ x^<9>-x $ на неприводимые множители над $ \mathbb Z_<> $: $$ x^<9>-x \equiv x(x-1)(x+1)(x^2+1)(x^4+1) \ . $$ Здесь полином $ x^2+1 $ должен быть неприводим по модулю $ 3_<> $. Полином $ x^4+1 $ должен раскладываться по модулю $ 3_<> $ на два множителя $ 2_<> $-й степени. Будем искать один из этих множителей методом неопределенных коэффициентов. Если взять его равным $ x^2+ax+b $, то результатом деления на него полинома $ x^4+1 $ будет $$ x^4+1 \equiv (x^2+ax+b)(x^2-ax+a^2-b)+a(2b-a^2)x+(b^2-a^2b+1) \ . $$ Коэффициенты остатка приравняем нулю по модулю $ 3_<> $: $$ a(2b-a^2)\equiv_<_<3>> 0 ,\ b^2-a^2b+1 \equiv_<_<3>> 0 \ . $$ Если из первого сравнения взять $ a \equiv_<_<3>> 0 $, то из второго сравнения получим $ b^2+1 \equiv_<_<3>> 0 $. Это сравнение решений не имеет 9) . Следовательно, из первого сравнения надо выбрать альтернативный вариант: $$ a^2 \equiv_<_<3>> 2 b \quad \iff \quad a^2 \equiv_<_<3>> -b ; $$ подставляем его во второе сравнение: $$ 2b^2+1 \equiv_<_<3>> 0 \quad \iff \quad — b^2+1 \equiv_<_<3>> 0 \quad \iff \quad b \equiv_<_<3>> \pm 1 \ . $$ Если $ b \equiv_<_<3>> 1 $, то $ a^2 \equiv_<_<3>> — 1 $ или $ a^2 \equiv_<_<3>> 1 $. Первое сравнение невозможно. Неприводимыми по модулю $ 3_<> $ полиномами $ 2_<> $-й степени являются $ x^2+x-1 $ и $ x^2-x-1 $. ♦</p>
<h3>Полиномы над GF(2)</h3>
<p>Наибольшую важность для приложений в теории кодирования имеют поля $ \mathbf<GF>(2^m) $. Рассмотрим примеры полей из полиномов с коэффициентами из множества $ \ <0,1 \>$ — о таких полиномах часто говорят как о <strong>полиномах над GF(2)</strong>. На этих примерах мы проиллюстрируем еще раз результаты предыдущих пунктов.</p>
<p>Заметим, что любой (не тождественно нулевой) полином из такого поля всегда нормализован.</p>
<p>Доказать, что любой неприводимый по модулю $ 2_<> $ полином степени $ n> 1 $ имеет нечетное число мономов.</p>
<p><strong>Пример.</strong> Исследовать поле $ \mathbf<GF>(16) $.</p>
<p><strong>Решение.</strong> Поле содержит $ 16_<> $ элементов: полиномов вида $ A_0x^3+A_1x^2+A_2x+A_3 $ при $ \ <A_0,A_1,A_2,A_3\>\in \ <1,2\>$. Теперь надо определить операцию умножения. Разложение полинома $ x^<16>-x $ на неприводимые по модулю $ 2_<> $ множители приведено в предыдущем пункте: $$ x^<16>-x \equiv_<_<2>> x(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^4+x^3+1)(x^4+x+1) \ . $$ При любом выборе неприводимого полинома $ f_<>(x) $ степени $ 4_<> $ из трех, участвующих в этом разложении, операция умножения по двойному модулю $ 2,f(x) $ будет удовлетворять аксиомам поля. Проверим это для выбора $ f_<>(x)=x^4+x+1 $. Следующая таблица выражает все полиномы из поля через посредство выражений для степеней $ \ <x^<k>\quad (\operatorname <modd>\ 2,f(x)) \>_<k=0>^ <14>$: $$ \begin<array> <l|rrrr|c|c>x^0 & & & & 1 & 0001 & \\ x^1 & & & x & & 0010 & \Pi \\ x^2 & & x^2 & & & 0100 & \Pi \\ x^3 & x^3 & & & & 1000 & \\ \hline x^4 & & & x & +1 & 0011 & \Pi \\ x^5 & & x^2 & +x & & 0110 & \\ x^6 & x^3 & +x^2 & & & 1100 & \\ x^7 & x^3 & & + x & +1 & 1011 & \Pi \\ \hline x^8 & & x^2 & & +1 & 0101 & \Pi \\ x^9 & x^3 & & +x & & 1010 \\ x^ <10>& & x^2 &+x & +1 & 0111 \\ x^ <11>& x^3 & +x^2 & +x & & 1110 & \Pi \\ \hline x^ <12>& x^3 & +x^2 & + x& +1 & 1111 \\ x^ <13>& x^3 & +x^2 & & +1 & 1101 & \Pi \\ x^ <14>& x^3 & & & +1 & 1001 & \Pi \end <array>$$ (и если бы мы продолжили эту таблицу, то следующим шагом вышли бы на цикл: $ x^ <15>\quad (\operatorname <modd>\ 2,f(x)) \equiv 1 $). В третьем столбце стоят двоичные наборы коэффициентов полиномов, рассматриваемых в разложении по убывающим степеням $ x_<> $. В четвертом столбце отмечены примитивные элементы поля, т.е. элементы, степени которых порождают все ненулевые элементы поля (одним из них являлся полином, тождественно равный $ x_<> $, по которому, собственно, и составлена таблица; с тем же успехом мы могли бы рассматривать и $ \ <\left(x^2\right)^k \quad (\operatorname<modd>\ 2,f(x)) \>_<k=0>^ <14>$ или $ \<\left(x^<11>\right)^k \quad (\operatorname <modd>\ 2,f(x)) \>_<k=0>^ <14>$, и т.п.). Количество примитивных элементов равно $ \phi(2^4-1)=\phi(15)=8 $. Все они обязаны удовлетворять алгебраическим уравнениям, степеней равных делителям числа $ 16_<> $. Все эти уравнения можно получить из разложения полинома $ x^ <16>— x $ на неприводимые по модулю $ 2_<> $ множители. Проверим это. Чтобы избежать путаницы, будем рассматривать неприводимые полиномы относительно переменной $ \mathfrak x $. Проверяем, что полиномы $ x, x^2,x^4,x^8 $ удовлетворяют уравнению $ \mathfrak x^4+\mathfrak x+\mathfrak e= \mathfrak o $; везде ниже сравнения вычисляются по двойному модулю $ 2,x^4+x+1 $: $$x^4+x+1 \equiv 0,\ (x^2)^4+(x^2)+1 \equiv x^8+x^2+1 \equiv x^2+1+x^2+1 \equiv 0, $$ $$ \begin <matrix>(x^4)^4+(x^4)+1 & \equiv &(x+1)^4+(x+1)+1 \equiv x+(x+1)+1 \equiv 0 , \\ (x^8)^4+(x^8)+1 & \equiv & (x^<2>+1)^4+(x^2+1)+1 \equiv x^2+(x^2+1)+1 \equiv 0 \ . \end <matrix>$$ Оставшиеся $ 4_<> $ примитивных элемента поля, именно, $ x^7,x^<11>,x^<13>,x^ <14>$ должны удовлетворять другому уравнению $ 4_<> $-й степени, которое соответствует одному из оставшихся неприводимых полиномов этой степени. В самом деле, они удовлетворяют уравнению $ \mathfrak x^4+\mathfrak x^3+\mathfrak e= \mathfrak o $: $$ (x^7)^4 + (x^7)^3+1 \equiv x^<28>+x^<21>+1 \equiv x^<13>+x^<6>+1\equiv x^3+x^2+1+(x^3+x^2)+1 \equiv 0 \ . $$ Последние вычисления проводились с учетом $ x^ <15>\equiv 1 $ и с использованием построенной выше таблицы для степеней $ x^ <k>$.</p>
<p>Примитивные элементы поля, т.е. элементы порядка $ 15_<> $, исчерпаны. Все остальные элементы поля имеют порядки, равные $ 1_<>, 3_<> $ или $ 5_<> $, т.е. — в соответствии с теоремой предыдущего пункта — делителям числа $ 15_<> $. Рассмотрим последовательность $ \ <\left(x^3\right)^k \quad (\operatorname<modd>\ 2,f(x)) \>_<k=0>^ <14>$: $$ (x^3)^0 \equiv 1,\ (x^3)^1 \equiv x^3,\ (x^3)^2 \equiv x^6 \equiv x^3 +x^2,\ (x^3)^3 \equiv x^9 \equiv x^3 +x,\ (x^3)^4 \equiv x^ <12>\equiv x^3 +x^2+x+1,\ (x^3)^5 \equiv x^ <15>\equiv 1 \ . $$ Итак, элемент поля $ x^ <3>$ принадлежит показателю $ 5_<> $, этому же показателю принадлежат и его степени, т.е. полиномы $ x^3 +x^2,\ x^3 +x,\ x^3 +x^2+x+1 $. Все эти полиномы удовлетворяют уравнению $ \mathfrak x^4+\mathfrak x^3+\mathfrak x^2+\mathfrak x+\mathfrak e= \mathfrak o $, соответствующему третьему неприводимому полиному $ 4_<> $-й степени из разложения $ x^<16>-x $. На всякий случай, осуществим выборочную проверку: $$ (x^9)^4+(x^9)^3+(x^9)^2+x^9+1 \equiv x^<6>+x^<12>+x^3+x^9+1 \equiv (x^3+x^2)+(x^3+x^2+x+1)+x^3+(x^3+x)+1 \equiv 0 \ . $$ Теперь рассмотрим оставшиеся элементы поля: $ x^5 $ и $ x^ <10>$. Они должны принадлежать показателю $ 3_<> $, что и немедленно проверяется. Кроме того, они должны удовлетворять неприводимому уравнению из разложения $ x^<16>-x $. Выбор однозначен — единственным кандидатом является уравнение $ 2_<> $-й степени $ \mathfrak x^2+ \mathfrak x + \mathfrak e = \mathfrak o $: $$ (x^5)^2+x^5+1 \equiv x^2+x+1 + (x^2+x)+1 \equiv 0 \ . $$ Наконец, нейтральные элементы поля $ 0_<> $ и $ 1_<> $ — с ними все просто. ♦</p>
<p><strong>Вывод.</strong> Поле Галуа одновременно обладает свойствами циклической группы, линейного пространства и алгебраического уравнения с целыми коэффициентами. С одной стороны, все ненулевые элементы поля можно представить как степени одного единственного. С другой стороны, операция сложения полиномов эквивалентна сложению векторов, составленных из их коэффициентов. Заметим, что в линейном пространстве не вводится аналога умножения векторов — такого, чтобы при умножении двух векторов получался снова вектор. С третьей стороны, все элементы поля разбиваются на подмножества, каждому из которых соответствует неприводимое алгебраическое уравнение — говорят, что <strong>элементы поля являются корнями неприводимых над GF(2) полиномов</strong>.</p>
<p>Для предыдущего примера составить аналоги таблицы степеней $ \ <\mathfrak a^<k>\quad (\operatorname <modd>\ 2,f(x)) \>_<k=0>^ <14>$ при выборе в качестве $ f_<>(x) $ <br /><strong>а)</strong> $ x^4+x^3+1 $; <strong>б)</strong> $ x^4+x^3+x^2+x+1 $; а также подходящего примитивного элемента $ \mathfrak a $.</p>
<p><strong>Решение</strong> ☞ ЗДЕСЬ.</p>
<p>Теперь займемся неприводимыми полиномами. Сначала оценим их число — в абсолютном количестве, а также в отношении к общему количеству полиномов степени $ k_<> $: $$ \begin<array> <c|c|c|c|c|c|c|c|c|c|c|c|c|c|c>k & 1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 12 & 21 & 25 & 30 \\ \hline \xi(k) & 2 & 1 & 2 & 3 & 6 & 9 & 18 & 30 & 56 & 99 & 335 & 99858 & 1342176 & 35790268 \\ \hline \xi(k)/2^k & 1 & 0.25 & 0.25 & 0.19 & 0.19 & 0.14 & 0.14 & 0.12 & 0.11 & 0.10 & 0.08 & 0.05 & 0.04 & 0.03 \end <array>$$</p>
<p>Разложить полином $ x^<64>-x $ на неприводимые по модулю $ 2_<> $ множители.</p>
<p><strong>Решение</strong> ☞ ЗДЕСЬ.</p>
<h3>Полиномы над GF(p)</h3>
<p>Теперь обобщим результаты разобранных в предыдущем пункте примеров. Будем рассматривать полиномы $ F_<>(x) $ над $ \mathbf<GF>(p) $. Нас будут интересовать решения уравнения $$ F(\mathfrak x) \equiv \mathfrak o \ . $$ среди элементов конечного поля $ \mathbf<GF>(p^m) $. Любой такой элемент $ \mathfrak a $ будем называть <strong>корнем полинома</strong> $ F_<> $ <strong>в поле</strong> $ \mathbf<GF>(p^m) $.</p>
<p><strong>Теорема 1.</strong> Пусть $ F_<>(x) $ — <em>неприводимый по модулю</em> $ p_<> $ <em>полином степени</em> $ n_<> $ <em>и</em> $ \mathfrak a \in \mathbf<GF>(p^m) $ — <em>его корень. Тогда множество корней</em> $ F_<>(x) $ <em>в поле</em> $ \mathbf<GF>(p^m) $ <em>совпадает с</em> $$ \mathfrak a, \mathfrak a^p, \mathfrak a^<p^2>,\dots, \mathfrak a^<p^<n-1>> \ . $$</p>
<p><strong>Доказательство.</strong> Воспользуемся теоремой Шёнеманна: для произвольного полинома $ F(x)\in \mathbb Z[x] $ выполняется $$ \left[F(x)\right]^p \equiv F(x^p) \pmod </p>
<p>\ . $$ Тогда если $ F(\mathfrak a)= \mathfrak o $, то и $ F(\mathfrak a^p)= \mathfrak o $, но тогда и $ F((\mathfrak a^p)^p)= \mathfrak o $, и т.д. С другой стороны, все элементы множества $ \ < \mathfrak a^<p^j>\>_<j=0>^ <n-1>$ различны. Действительно, если бы выполнялось равенство $$ \mathfrak a^<p^j>=\mathfrak a^ <p^k>\qquad npu \qquad 0\le j< k \le n-1 \ , $$ то возведением его в степень $ p^ <n-k>$, получим равенство $$ \mathfrak a^<p^<n+j-k>>=\mathfrak a^ <p^n>= \mathfrak a \ . $$ Последнее равенство следует из доказательства теоремы из ☞ ПУНКТА. Однако равенство $$ \mathfrak a^<p^<n+j-k>>= \mathfrak a $$ невозможно, поскольку $ n+j-k< n $, а, ввиду теоремы 3 из ☞ ПУНКТА, полином $ x^<p^<n+j-k>>-x $ делится лишь на такие неприводимые по модулю $ p_<> $ полиномы, степени которых являются делителями числа $ n+j-k $ и, следовательно, не может делиться на $ F_<>(x) $. ♦</p>
<p><strong>Теорема 2.</strong> <em>Все корни неприводимого полинома</em> $ F_<>(x) $ <em>принадлежат одному показателю (имеют одинаковый порядок).</em> </p>
<p>Показатель корней неприводимого полинома называется <strong>показателем</strong>, которому этот полином принадлежит. Если неприводимый полином $ F_<>(x) $ принадлежит показателю $ \ell_<> $, то он является делителем полинома $ x^<\ell>-1 $, но не является делителем ни одного из полиномов $ x^k-1 $ при $ k\in \ <1,\dots,\ell-1 \>$. Неприводимый полином степени $ m_<> $ над $ \mathbf<GF>(p) $ называется <strong>примитивным</strong>, если его корнем является примитивный элемент поля $ \mathbf<GF>(p^m) $. В этом случае, этот корень принадлежит показателю $ p^m-1 $, и по теореме 2, все корни $ F_<>(x) $ принадлежат тому же показателю, т.е. являются примитивными элементами поля.</p>
<p>Число неприводимых полиномов степени $ m_<>>1 $ равно $ \phi (p^m-1)/m $.</p>
<p>Неприводимый полином $ F_<>(x) $ степени $ m_<> $ является примитивным тогда и только тогда, когда он не является делителем ни одного из полиномов $ x^k-1 $ при $ k\in \ <1,\dots,p^m-2 \>$. Если каноническое разложение числа $ p^m-1 $ имеет вид:</p>
<p>$$ p^m-1=p_1^<<\mathfrak m>_<_1>>p_2^<<\mathfrak m>_<_2>>\times \dots \times p_<\mathfrak r>^<<\mathfrak m>_<_<\mathfrak r>>> \ , $$ то для того чтобы неприводимый полином $ F_<>(x) $ степени $ m_<> $ был примитивным, необходимо и достаточно, чтобы он не являлся делителем ни одного из полиномов $ x^<(p^m-1)/p_j>-1 $ при $ \forall j \in \ <1,\dots, \mathfrak r \>$.</p>
<p><strong>Пример.</strong> Из трех неприводимых полиномов $ 4_<> $-й степени:</p>
<p>$$ x^4+x+1, \ x^4+x^3+1, \ x^4+x^3+x^2+x+1 $$ примитивными будут только первый и второй. Подробный разбор см. ☞ ЗДЕСЬ.</p>
<p><strong>Пример.</strong> Примитивные полиномы $ 6_<> $-й степени см. ☞ ЗДЕСЬ.</p>
<h2>Источники</h2>
<p>[1]. <strong>Чеботарев Н.</strong> <em>Основы теории Галуа. Часть I.</em> М.-Л.ОНТИ. 1934.</p>
<p>[2]. <strong>Питерсон У., Уэлдон Э.</strong> <em>Коды, исправляющие ошибки.</em> М.Мир. 1976.</p>
<p>[3]. <strong>Лидл Р., Нидеррайтер Г.</strong> <em>Конечные поля. Том 1.</em> М.Мир. 1988.</p>
<p>[4]. <strong>Ротман Т.</strong> <em>Короткая жизнь Эвариста Галуа.</em> Scientific American. N 1, 1983, cc. 84-93. Текст ☞ ЗДЕСЬ.</p>
<div class='yarpp yarpp-related yarpp-related-website yarpp-template-list'>
<!-- YARPP List -->
<div>Похожие публикации:</div><ol>
<li><a href=](https://habrastorage.org/webt/zb/5h/ej/zb5hejuapdli4_sqrwbuhlbb3sq.png "Как сформировать торг 29 в 1с бухгалтерия")
Как сформировать торг 29 в 1с бухгалтерия