3.2. ПОСТРОЕНИЕ ПОЛЯ GF(16)

Ясно, что последовательности длины 4 из элементов 0 и 1 можно складывать как векторы, а вычитание в нашем случае совпадает со сложением. Более того, Мы

должны, однако, определить умножение. Для этого сопоставим каждому 4-вектору многочлен от а:

Умножение двух таких многочленов часто дает многочлен степени, большей чем 3, т. е. нечто, не принадлежащее нашему множеству объектов.

Так, например,

Мы хотим свести ответ к многочлену степени не более 3. Для этого условимся, что а удовлетворяет некоторому фиксированному уравнению степени 4; подходящее уравнение имеет вид

Тогда так что

Это эквивалентно делению на многочлен и нахождению остатка от деления:

Таким образом, произведение двух -векторов 1101 и 1001; равно

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

Аналогично

Теперь, если введенное нами умножение должно быть обратимо (что необходимо для того, чтобы наша система элементов образовывала поле), то многочлен должен быть неприводим над полем

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

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

Теорема 1. Если неприводим, то каждый ненулевой многочлен степени не более 3 имеет единственный обратный многочлен такой, что

Доказательство. Рассмотрим произведения где пробегает все многочлены

степени не более 3. Все эти произведения должны быть различными по модулю потому, что если то и (в силу неприводимости многочлена ) либо либо Так как степени многочленов меньше, чем степень то это может выполняться только в случае, когда Таким образом, все произведения различны, и поэтому с точностью до перестановки они должны совпадать с множеством (3.5). В частности, только для одного многочлена должно выполняться равенство и тогда

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

решение которой: Следовательно, обратный элемент равен

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

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

Проверим теперь, что многочлен неприводим. Его степень равна 4, и поэтому, если он не является неприводимым, то содержит делители степени 1 или 2. Единственными многочленами степени 1 являются Ясно, что Если то Но и поэтому

Что теперь можно сказать о делителях степени 2? Сразу же исключим многочлены Остается единственный многочлен который мы можем проверить с помощью деления, используя только одни коэффициенты:

Следовательно, многочлен неприводим.

Таким образом, мы превратили в поле 16 векторов длины 4 из элементов 0 и 1. Это поле называется полем Галуа порядка 16, сокращенно GF(24) или

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

Рис. 3.1. Поле GF(24), порожденное элементом а, где

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

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

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

Любой ненулевой элемент у поля GF(24) может быть единственным образом представлен в виде степени а; пусть для (Конечно, Тогда число называется логарифмом (или, иногда, индексом) элемента у. При этом удобно положить, что

Полезно сопоставить первое представление элементов поля (столбцы 1 и 2 на рис. 3.1) с представлением комплексного числа в декартовых координатах: а второе (столбцы 3 и 4) — с представлением этого числа в полярных координатах: Первое представление удобнее для сложения, в то время как второе — удобнее для умножения.

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

Пример. Умножение элементов 0111 и 1111:

Но поэтому ответ таков:

Нахождение обратного элемента:

Нахождение квадратного корня:

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

В частности, если в качестве выбрать примитивный неприводимый многочлен степени над полем GF(2), то получим поле из всех двоичных векторов длины