2.5. Конечные поля

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

Теорема 2.4. Конечное поле является векторным пространством над любым своим подполем

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

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

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

Теорема 2.5. Если поле характеристики то его порядок является степенью

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

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

Из теоремы 2.4, в частности, следует, что любое конечное поле является векторным пространством над некоторым полем порядок которого есть простое число. Элементы этого векторного пространства, называемые ниже векторами, можно представить различными способами. Например, их можно представить в виде последовательностей из элементов поля (утверждение 2.29). С другой стороны, каждому вектору можно сопоставить многочлен

Если ввести операции сложения многочленов и умножения многочлена на константу посредством соотношений (2.8) и (2.10), то эти операции будут в точности соответствовать сложению и умножению на константу соответствующих последовательностей символов длины Это позволяет рассматривать множество многочленов степени и менее и последовательности символов длины как различные представления одного и того же векторного пространства. Представление произвольной бесконечной последовательности элементов некоторого множества в виде формального многочлена

является хорошо известным и широко применяемым приемом. Такие многочлены иногда называют производящими функциями или формальными степенными рядами. При представлении

последовательностеи в виде формальных многочленов символ X используется лишь для указания положения элементов в исходной последовательности и не является некотррым «неизвестным элементом». В силу этого символ X был назван формальной переменной. Как мы уже знаем, конечное поле является векторным пространством размерности над полем порядок которого есть простое число. Поэтому любой элемент (вектор) поля можно представить в виде многочлена степени над полем Однако само по себе это представление будет не очень интересным, если не указать, каким образом следует складывать и умножать элементы поля представленные в виде многочленов. Выше мы ввели сложение векторов, но не касались их умножения. Если представить векторы в виде многочленов то можно ввести операцию умножения векторов, используя для этого умножение многочленов. Однако, как показывает доказательство свойства 5 из утверждения 2.37, при таком определении умножения элементы могут не иметь обратных не является полем. Более того, при представлении элементов поля в виде многочленов степени из при обычном умножении многочленов из может получиться многочлен степени или выше, а это означает, что обычное умножение многочленов оказывается не замкнутой в операцией Ключом к построению конечных полей порядка простое число) является разложение кольца многочлена на классы вычетов по некоторому специально выбранному модулю Аналогичный прием использовался и при построении полей вида когда были введены операции по модулю

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

Пусть некоторый неприводимый многочлен степени Используя разложим на классы еле дующим образом. Отнесем к одному классу все многочле которые дают один и тот же остаток при делении Класс, содержащий многочлен обозначим через Два многочлена принадлежат одному тогда и только тогда, когда делится на Это мы будем записывать в виде Полученные таким образом классы будем называть классами вычетов по модулю Множество всех классов вычетов по модулю обозначим через Поскольку существует взаимно однозначное соответствие между классами вычетов и многочленами из то ясно, что число классов вычетов равно Введем в операции сложения и умножения

следующим образом. Для любых положим

При таком определении сложения и умножения классы вычетов (1) и (0) оказываются соответственно единичным и нулевым элементами Пусть Так как многочлены взаимно просты, то, согласно утверждению 2.41, существует единственный многочлен такой, что

Следовательно,

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

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

Обозначим через а класс вычетов , содержащий многочлен Пусть Тогда

Это означает, что многочлен имеет корень а в поле Многочлен является неприводимым над полем и уравнение не имеет решений в поле Однако, как мы только что показала уравнение имеет решение в поле . В этом смысле поле является расширением поля

полученным присоединением к корня уравнения Каждый элемент поля можно представить в виде

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

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

Задача 2.50. Показать, что элементы образуют базис

Построим несколько конечных полей указанным выше способом.

Задача 2.51. Построить поле порядка

Решение. В качестве неприводимого многочлена второй степени над возьмем многочлен (задача 2.44). Каждый элемент поля имеет вид где Найдем сумму и произведение элементов

Эти формулы напоминают соответствующие формулы для вычисления суммы и произведения комплексных чисел. Отличие состоит лишь в том, что в последних вместо X обычно стоит мнимая единица

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

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

Задача 2.52. Построить поле порядка 23, используя неприводимый многочлен

Решение. Положим и рассмотрим следующие восемь классов вычетов по модулю

Определим сложение и умножение этих классов вычетов следующим образом:

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

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

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

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

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

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

Теорема 2.7. Любой элемент конечного поля порядка является корнем уравнения

Доказательство. Пусть а — один из примитивных элементов ноля произвольный элемент Элемент можно представить в виде некоторой степени элемента а, т. е.

Тогда Следовательно, любой элемент из является корнем уравнения

Утверждение 2.53. Пусть а — целое положительное число, минимальное целое положительное число, такое, что а Тогда

3) существует такое что

Доказательство. Пусть Тогда Так как то Если то поскольку по определению Второе утверждение следует из первого.

Чтобы доказать третье утверждение, рассмотрим следующую последовательность целых чисел: где остаток от деления на а. Так как число различных остатков при делении на а не может превышать а, то найдутся такие что т. е. Так как то в силу свойства целых чисел т. е. Таким образом, мы доказали, что если то существует такое целое что Использованный здесь метод доказательства будет применяться в дальнейшем неоднократно. Доказательство обратного утверждения предоставляется провести читателю самостоятельно.

Запись часто используемая ниже, означает, что многочлен делит многочлен

Утверждение 2.54.

Пусть минимальное целое число, такое, что называется показателем Тогда

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

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

является неприводимым. Действительно, если предположить, что то из определения непосредственно будет следовать, что Но тогда в силу свойства 2 поля из утверждения 2.22 либо либо в содержится многочлен, степень которого меньше, чем степень т. е. мы получили противоречие. Далее заметим, что все многочлены из должны делиться на Действительно, допустим, что в содержится многочлен который не делится на Тогда, как мы знаем, существуют многочлены такие, что

Подставим в последнее равенство вместо X элемент а. Тогда, так как опять получаем, что в содержится многочлен, степень которого меньше, чем степень что противоречит определению Следовательно, все многочлены из — это многочлены вида . В частности, отсюда следует, что минимальный многочлен элемента а определяется однозначно.

Теорема 2.8. Пусть поле порядка нормированный неприводимый многочлен степени тип — показатель Тогда минимальное целое число, такое, что . В частности, если то называется примитивным многочленом.

Доказательство. Пусть элемент поля Как мы уже видели выше, Так как — неприводимый многочлен, то Согласно теореме 2.7, а является корнем уравнениях — так что Отсюда и из утверждения 2.54 следует, что Допустим, что Тогда поскольку Как указывалось выше, любой элемент поля может быть представлен в виде

Из теоремы 2.7 имеем . Поскольку, кроме того, поручаем (см. задачу 2.27)

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

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

Доказательство. Согласно утверждению 2.53,

Но тогда из утверждения 2.54 получаем

Из, теоремы 2.8 следует, что минимальное для которого равно

Из единственности разложения любого многочлена на неприводимые множители (утверждение 2.42), из того, что многочлен не имеет кратных множителей (утверждение 2.48), и из теоремы 2.9 следует справедливость следующей теоремы.

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

Обозначим через число неприводимых нормированных многочленов степени входящих в Очевидно, что Из теоремы 2.10 непосредственно получаем, что для любого целого

где сумма берется по всем делителям числа (включая Отсюда следует, что

Но тогда

откуда

и

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

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

Теорема 2.11. Для любого простого числа и любого целого положительного существует конечное поле порядка

В случае конечных групп, как мы уже видели выше (задача 2.4), из равенства порядков групп еще не следует их изоморфизм. Однако все поля одного и того же порядка изоморфны. Докажем это.

Пусть произвольное конечное поле, являющееся расширением поля Пусть Возьмем произвольный многочлен из степень которого является делителем (как следует из теорем 2.4 и 2.10, это всегда можно сделать). Этот многочлен является минимальным многочленом некоторого элемента а поля Пусть степень Рассмотрим следующее подмножество поля

Сопоставим каждому элементу элемент Заметим, что это отображение является взаимно однозначным, и если

то

т. е. отображение сохраняет операцию сложения. Пусть Поскольку то

Покажем, что все элементы вида поля принадлежат Так,

Аналогично можно доказать, что и остальные элементы принадлежат Отсюда следует, что если то С другой стороны, в

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

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

Теорема 2.12. Все конечные поля одного и того же порядка изоморфны. Другими словами, конечное поле заданного порядка единственно с точностью до обозначения элементов.

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

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

Теорема 2.13. Пусть поле, являющееся расширением поля и пусть Тогда показатель минимального многочлена элемента равен порядку элемента Степень многочлена является минимальным целым положительным числом, таким, что ; при этом Корнями уравнения являются следующие различных элементов .

Доказательство. Так как то . С другой стороны, если , то Следовательно, показатель равен Из теоремы 2.8 следует, что степень многочлена является минимальным целым положительным числом, таким, что Кроме того, из теоремы 2.6 следует, что Но тогда, согласно утверждению Пусть Тогда, так как и

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

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

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

Как следует из теоремы 2.13 и доказательства теоремы 2.8, неприводимый многочлен степени из имеет различных корней в поле т. е. в силу теоремы 2.12 в поле Таким образом, многочлен не имеет корней в поле и в то же время имеет различных корней в

Утверждение 2.55. Пусть минимальный многочлен элемента а. Если является корнем уравнения то Все корни минимального многочлена имеют один и тот же порядок.

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

так что Следовательно,

Утверждение 2.56. Пусть а — произвольный элемент из Тогда, если порядок а равен х, то порядок элемента а равен

Доказательство следует из утверждения 2.2 и теоремы 2.6.

Утверждение 2.57. Пусть Тогда имеет ровно примитивных элементов функция Эйлера).

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

тогда, когда но количество целых чисел для которых выполняется последнее неравенство, равно по определению

Пусть многочлен степени Многочлен называется двойственным к многочлену

Многочлен для которого называется самодвойственным. Если то где элемент, обратный к

Утверждение 2.58.

1) Многочлен неприводим тогда и только тогда, когда неприводим многочлен

2) Многочлен является примитивным тогда и только тогда, когда примитивным является многочлен

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

Пусть Разобьем числа от 0 до на -циклы. Пусть циклы, содержащие Возьмем некоторый примитивный элемент а поля и рассмотрим минимальный многочлен элемента Тогда, согласно теореме 2.13, корни уравнения это элементы Степень равна длине цикла. Таким образом, мы установили соответствие между циклами и минимальными многочленами (фиксировав предварительно примитивный элемент).

Задача 2.59. Рассмотрим поле Используя неприводимый над многочлен четвертой степени составить таблицу соответствия представлений элементов поля в виде степеней примитивного элемента и многочленов. Найти минимальный многочлен элемента

Решение. Таблицу соответствия следует составлять последовательно так, как это было описано при доказательстве теоремы 2.12:

Как видно из доказательства теоремы 2.8, минимальным многочленом элемента а является сам многочлен Однако можно найти также следующим образом. Так как, согласно теореме 2.13, все корни это элементы то

Задача 2.60. В случае разбив совокупность целых чисел от 0 до на -циклы и выбрав в качестве минимального многочлена, соответствующего циклу, содержащему 1, многочлен найти минимальные многочлены, соответствующие другим циклам.

Решение. Совокупность целых чисел от 0 до 24 — 2 разбивается на циклы следующим образом:

Циклу, содержащему 0, соответствует минимальный многочлен 1. Циклу, содержащему 3, соответствует минимальный

многочлен

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

Полученные выше многочлены являются самодвойственными. Поэтому наряду с корнем а они имеют в качестве корня также и Так как в данном случае то Из таблицы циклов легко видеть, что минимальный многочлен, соответствующий циклу, содержащему числа 5 и 10, также является самодвойственным и имеет степень 2. Имеются два многочлена, удовлетворяющие этому условию: Однако т. е. многочлен не является неприводимым. Следовательно, минимальным многочленом, соответствующим циклу, содержащему 5, является Наконец, рассмотрим последний цикл, содержащий число 14. Поскольку то минимальные многочлены, соответствующие циклу, содержащему 1, и циклу, содержащему 14, двойственны друг другу. Следовательно, минимальным многочленом, соответствующим циклу, содержащему 14, является многочлен

В приведенном выше примере

Это соответствует случаю, когда в теореме Порядок каждого сомножителя является делителем числа 4.

Найдем порядки элементов когда числа принадлежат различным циклам. Из утверждения 2.55 получаем

Пусть совокупность корней уравнения Разбив эту совокупность на группы элементов, имеющих

один и тот же порядок, и введя многочлены

получим

Многочлены, имеющие своими корнями все элементы одного и того же порядка, называются круговыми. В приведенном выше примере

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

Фиг. 2.1.

Согласно теореме 2.13, является минимальным многочленом в том и только том случае, если степень является минимальным целым числом таким, что приведенном выше примере минимальные многочлены. Однако поскольку минимальное число такое, что равно 4, то представляет собой произведение двух неприводимых многочленов.

Разделим окружность на 15 равных частей с помощью 15 точек, которые обозначим в порядке их расположения на окружности через Исследуем взаимосвязь между положением на окружности корней многочленов и полученными выше соотношениями (фиг. 2.1).

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

Задача 2.61. Разложить на множители многочлен над полем

Решение. Сначала построим все -циклы:

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

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

Следовательно,

Эта задача дает пример разложения в простом поле [поле называется простым, если оно не содержит других полей, кроме самого себя; как мы видели выше, поле может содержать только одно подполе, изоморфное простое число (теорема 2.3)]. Остановимся кратко на полях, не являющихся простыми.

Задача 2.62. Поле является подполем поля тогда и только тогда, когда

Задача 2.63. Разложить двучлен в произведение неприводимых над многочленов.

Решение. Будем считать, что, кроме элементов 0 и 1, поле содержит также корни многочлена Элемент (а следовательно, и является примитивным элементом поля Представление элементов поля в виде степеней примитивного элемента будет следующим:

Чтобы разложить в произведение неприводимых над многочленов, необходимо построить все -циклы:

Если сравнить эту таблицу циклов с таблицей -циклов из задачи 2.60, то можно заметить, что первая таблица получается разбиением каждого цикла второй таблицы (за исключением цикла 0) на два цикла. Используя примитивный элемент а из задачи 2.60, многочлен, соответствующий -циклу, содержащему число 3, можно преобразовать следующим образом:

Из вышеизложенного (см задачу 2.59) имеем Оба элемента имеют порядок 3 и являются элементами поля Следовательно,

Аналогично преобразовывая многочлены, соответствующие другим циклам, получим

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

1. Выбирается -ичный код).

2. Выбирается (длина кода).

3. Находится минимальное такое, что и берется поле

4. Из элементов поля выбирается один, имеющий порядок Этот элемент обозначается через и считается фиксированным; -циклу, содержащему 1, сопоставляется многочлен После этого находятся минимальные многочлены, соответствующие другим интересующим нас циклам.

Задача 2.64. Разложить двучлен в произведение неприводимых над многочленов.

Решение. Построим таблицу -циклов: О

Следовательно, двучлен является произведением и двух неприводимых многочленов 11-й степени, двойственных друг другу. Эти неприводимые многочлены в принципе можно найти так же, как и раньше, но такой способ очень сложен. Для нахождения двух сомножителей 11-й степени воспользуемся таблицами, помещенными в приложении. Поскольку порядок корня двучлена равен 23, то сначала найдем такие целые числа что Поскольку, как следует из табл. то Если а — примитивный элемент поля то будет элементом порядка 23. Из табл. находим, что неприводимым многочленом 11-й степени, имеющим своим корнем элемент является многочлен Этот многочлен соответствует указанному выше циклу, содержащему 1. Другой

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

Неприводимые многочлены 11-й степени в правой части последнего разложения являются порождающими многочленами кода Голея.