Главная > Математика > Основы компьютерной алгебры с приложениями
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.3.2. Построение полей Галуа GF(2^r)

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

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

Мы начинаем с двух элементов 0 и 1 из GF(2) и символа а. Определяем умножение для элементов из GF(2) и а следующим образом: затем полагаем а и т. д. Заметим, что из данного определения следует

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

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

Покажем теперь, что F — (мультипликативная) группа относительно умножения, замкнутой в F операции. Прежде всего заметим, что элемент 1 — единичный элемент. Затем возьмем два элемента из F и рассмотрим их произведение . Если , то это элемент из F и ничего делать не нужно; однако если , то , где — элемент из F. Более того, каждый элемент а имеет мультипликативный обратный, равный Поэтому F — коммутативная группа относительно умножения порядка

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

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

Заметим, что если мы разделим на то получим над GF(2), т.е. Поскольку не делит x, и поэтому для любого Более того, для [В этом мы убеждаемся от противного. Предположим, что для . Тогда из выражений получаем ]. Из последнего равенства следует, что при условии, конечно, что Так как не делит то — полином степени это и есть необходимое противоречие, поскольку с - примитивен. Поэтому для мы получаем различных ненулевых полиномов степени Заменяягнаав выражениих получаем

Таким образом, из этого соотношения видно, что каждый элемент из F единственным способом представляется в виде полинома от а над GF(2) степени Нулевой элемент из F представляется нулевым полиномом. Следовательно, сложение в F можно рассматривать как сложение полиномов, и нам известно, как делать это над Теперь легко можно проверить, что F — коммутативная группа по сложению, а вместе с предыдущими результатами это означает, что F — поле.

До настоящего времени мы имели дело с двумя представлениями поля степенное представление (удобное при умножении) и полиномиальное представление (удобное при сложении); см. также табл. 3.3.1. Существует также третье представление, получаемое, если представлять полином вектором его коэффициентов. Определяя -кортеж

как вектор над GF(2), получаем очевидным образом векторное представление поля Отметим, что существует различных векторов длины . Сложение векторов выполняется покомпонентно, и результат сложения — снова вектор; следовательно, оно весьма удобно для сложения элементов поля Умножение вектора v на скаляр s определяется правилом

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

Скалярное произведение двух векторов определим формулой Если скалярное произведение двух векторов равняется нулю, то векторы называются ортогональными.

Пример. Пользуясь с-примитивным полиномом построим поле Элементы получаются повторным применением равенства где в табл. 3.3.1 для них даны описанные выше три представления. Например, и т.д. Для перемножения двух элементов мы просто складываем их показатели степени и пользуемся тем, что например, Кроме того, Для сложения мы используем либо полиномиальное, либо векторное представление элементов и выполняем сложение покомпонентно.

<< Предыдущий параграф Следующий параграф >>
Оглавление