Какое поле называется полем галуа

Арифметика полей Галуа для кодирования информации кодами Рида-Соломона

На хабре есть пост посвященный кодированию информации кодами Рида-Соломона, но для примера автор использует простое поле Галуа. В данной статье описывается работа с расширенными полями Галуа, в частности GF(2^m), которые рационально использовать для цифровой информации.

При работе с кодами Рида-Соломона процент избыточных символов в 2 раза больше восстанавливаемого объема данных. Объясню на примере: если мы имеем последовательность из 10 символов и хотим иметь возможность восстановить ошибки в 3-ех из них (30% исходной информации), то нам нужно хранить 10+3*2=16 символов. Назовем каждую переменную: n = 10, количество информационных символов; f = 3, количество восстанавливаемых символов; g = 16, длина закодированной последовательности. Таким образом, формулу можно записать так: g = n + f * 2.

Поля Галуа

Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа. Таким образом, результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т.е. количество его элементов, является некоторой натуральной степенью характеристики pm, где m∈N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m, такое поле называется расширенным. GF(p^m) – обозначение поля Галуа.

Для работы с цифровыми данными естественно использовать p=2 в качестве характеристики поля. При m=1 элементом кодовой последовательности будет бит, при m=8 – 8 бит, то есть байт. Собственно коды Рида-Соломона работающие с байтами и являются наиболее распространенными.

Перед тем как переходить к операциям кодирования и декодирования разберемся с арифметикой полей Галуа на примере GF(2^3). Данное поле состоит из чисел от 0 до 7.

Операция сложения

Самой простой является операция сложения, которая является простым побитовым сложение по модулю 2 (ХОR).

Операция умножения

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

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

Перемножим два числа в полиномиальной форме:
5∙7=(x^2+1)∙(x^2+x+1)=x^4+x^3+x^2+x^2+x+1=x^4+x^3+x+1=11011=27

Итак, во-первых, следует заметить, что даже в полиномиальной форме осуществляется сложение по модулю 2, поэтому x^2+x^2=0. Во-вторых, результат умножения 27 не входит в используемое поле GF(2^3) (оно же состоит из чисел от 0 до 7, как было сказано выше). Чтобы бороться с этой проблемой, необходимо использовать порождающий полином. Порождающий полином является неприводимым, то есть простым (по аналогии с простыми числами делится без остатка на 1 и на самого себя). В арифметике полей Галуа неприводимым полиномом является аналог простых чисел. Используем для примера порождающий полином f(x)=x^3+x+1.

Также предполагается, что x удовлетворяет уравнению f(x)=x^3+x+1=0

Вернемся к примеру с умножением:

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

Составим таблицу умножения:

Операция деления

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

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

Таким образом, составим таблицу степеней:

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

В полях Галуа существует понятие примитивного члена – элемент поля, чьи степени содержать все ненулевые элементы поля. Просмотрев таблицу степеней видно, что этому условию соответствуют все элементы (ну кроме 1 естественно). Однако это выполняется не всегда, для примера приведу таблицу степеней для GF(16).

Для полей, которые мы рассматриваем, то есть с характеристикой 2, в качестве примитивного члена всегда выбирают 2. Учитывая его свойство, любой элемент поля можно выразить через степень примитивного члена.
Пример: 5=26, 7=25

Воспользовавшись этим свойством, и учитывая цикличность таблицы степеней, попробуем снова перемножить числа:
5∙7=2^6∙2^5=2^(6+5)=2^11=2^(11 mod 7)=2^4=6
Результат совпал с тем, что мы вычислили раньше.

А теперь выполним деление:
6÷5=2^4÷2^6=2^(4-6)=2^(-2)=2^((-2)mod 7)=2^5=7
Полученный результат тоже соответствует действительности.

Ну и для полноты картины посмотрим на возведение в степень:
5^2=(〖2^6)〗^2=2^(6∙2)=2^12=2^(12 mod 7)=2^5=7
Опять неожиданно получился такой же результат.

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

• коды рида-соломона
• галуа

VMath

Сложный для понимания материал! Желающим сначала быстро понять как применяется эта теория к задачам помехоустойчивого кодирования — см. ☞ ЗДЕСЬ.

Поля Галуа

В настоящем разделе буква $ p_<> $ обозначает простое число.

Структура конечного поля

Существование конечных полей, т.е. полей, состоящих из конечного числа элементов установлено в пункте ☞ ПОЛЕ.

Пример. Множество $ \mathbb Z_

$ классов вычетов по простому модулю $ 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\>_ $ должны повторяться. Если $ \mathfrak a_k= \mathfrak a_ $ при $ k= \mathfrak a_-\mathfrak a_k = \mathfrak o \ . $$ Таким образом, в рассматриваемой последовательности обязательно встретятся нулевые элементы.

Теорема 1. Пусть первый нулевой элемент последовательности $ \ <\mathfrak a_j\>$ имеет номер $ M_<> $: $$ \mathfrak a_M=\mathfrak o, \mathfrak a_j \ne \mathfrak o \quad npu \quad j\in \ . $$ Число $ M_<> $ — простое. Все элементы $ \mathfrak a_1,\dots,\mathfrak a_ $ различны.

Доказательство. Если $ M_<> $ — составное: $ M=M_1M_2 $ при $ M_1\cdot \mathfrak a_ \ . $$ Оба элемента $ \mathfrak a_ $ и $ \mathfrak a_ $ по предположению, ненулевые, а их произведение — нулевой элемент. Но это противоречит свойству поля. Оставшееся утверждение теоремы докажите самостоятельно. ♦

Простое число $ M=p_<> $ из предыдущей теоремы называется характеристикой конечного поля.

Теорема 2. Порядок (число элементов) любого конечного поля равен некоторой степени его характеристики: $$ \operatorname (\mathbb F) = p^m \quad \mbox < при >\quad p \mbox < - простом и >\quad m \in \mathbb N \ . $$

Доказательство. В предыдущей теореме было доказано, что конечное поле $ \mathbb F $ характеристики $ p_<> $ содержит $ p_<> $ различных элементов: $$ \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_ \quad npu \quad \mathfrak a_j= \underbrace<\mathfrak e + \dots+ \mathfrak e>_ \ . $$ Это множество обладает всеми свойствами поля и изоморфно полю $ \mathbb Z_p $. Изоморфизм устанавливается соответствием $ \mathfrak a_j \mapsto \overline j $. Действительно, по предположению $ \mathfrak a_p= \mathfrak o $, но тогда $$ \mathfrak a_= \mathfrak a_1, \mathfrak a_= \mathfrak a_2, \dots , \mathfrak a_= \mathfrak a_j, \dots , $$ а следовательно, $ \mathfrak a_j+ \mathfrak a_k=\mathfrak a_=\mathfrak a_< j+k \pmod

> $. Таким образом $ \mathfrak a_j+ \mathfrak a_k \mapsto \overline $, т.е. соответствие сохраняет результат сложения. Результат умножения также сохраняется, поскольку на основании свойств поля (в частности, дистрибутивности умножения относительно сложения), следует $$ \mathfrak a_j \cdot \mathfrak a_k=\mathfrak a_ = \mathfrak a_> \ , $$ т.е. $ \mathfrak a_j \cdot \mathfrak a_k \mapsto \overline $.

Установленный изоморфизм позволяет утверждать, что любой элемент $ \mathfrak a_j \ne \mathfrak o $ имеет обратный среди чисел того же множества: $ \mathfrak a_^ = \mathfrak a_ $, где $ s_<> $ — число, обратное $ j_<> $ относительно умножения по модулю $ p_<> $.

Если в поле $ \mathbb F $ нет других элементов, то $ \mathbb F = \< \mathfrak a_j \>_^ $ и теорема доказана: $ \operatorname (\mathbb F) = p $. Предположим, что существует $ \mathfrak A \in \mathbb F $ и $ \mathfrak A \not\in \< \mathfrak a_j \>_^ $. Тогда множество $$ \<\mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \>_^ $$ определяет $ p^2 $ различных элементов поля $ \mathbb F $. Действительно, если $$ \mathfrak a_>+ \mathfrak a_> \cdot \mathfrak A = \mathfrak a_>+ \mathfrak a_> \cdot \mathfrak A ,\ \mbox < то >\quad \mathfrak a_>- \mathfrak a_>=(\mathfrak a_>-\mathfrak a_>) \mathfrak A \ . $$ Если $ \mathfrak a_>-\mathfrak a_> \ne \mathfrak o $, то, по доказанному в предыдущем абзаце, существует обратный к элементу $ \mathfrak a_>-\mathfrak a_> $ и этот элемент находится в том же множестве $ \< \mathfrak a_j \>_^ $. Тогда из последнего равенства следует, что $$ \mathfrak A=(\mathfrak a_>-\mathfrak a_>)^ (\mathfrak a_>- \mathfrak a_>) \quad \Rightarrow \quad \mathfrak A \in \< \mathfrak a_j \>_^ \ , $$ что противоречит предположению. Если же $ \mathfrak a_>- \mathfrak a_> = \mathfrak o $, то тогда и $ \mathfrak a_>-\mathfrak a_> = \mathfrak o $.

Если в поле $ \mathbb F $ нет других элементов, то $ \mathbb F =\< \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \>_^ $ и $ \operatorname (\mathbb F) = p^2 $. В противном случае, существует элемент $ \mathfrak B_<> $, не входящий в это подмножество, и мы рассмотрим множество $$ \ < \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A + \mathfrak a_\cdot \mathfrak B \>_^ \ , $$ которое определяет $ p^3 $ различных элементов поля $ \mathbb F $. Дальнейший ход доказательства аналогичен предыдущим рассуждениям. Поскольку, по предположению, число элементов поля конечно, то процесс должен завершиться за конечное число шагов и если последний шаг имеет номер $ m_<> $, то получим утверждение теоремы. ♦

Пример. Рассмотрим поле, состоящее из $ 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 $, что незаконно.

Наконец, $$ \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 \mathbb & \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 $$ ♦

Итак, цепочкой рассуждений мы пришли к выводу: если существует конечное поле из $ 4_<> $-х элементов, то в нем операции сложения и умножения должны производиться по единственно возможным сценариям, которые описываются полученными таблицами. Однако, остался открытым вопрос:

Нет ли противоречий в этих построенных таблицах?

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

Пример. Рассмотрим множество, состоящее из квадратных матрицы второго порядка

$$ \mathfrak o= \left( \begin 0 & 0 \\ 0 & 0 \end \right),\ \mathfrak e= \left( \begin 1 & 0 \\ 0 & 1 \end \right),\ \mathfrak a= \left( \begin 1 & 1 \\ 1 & 0 \end \right),\ \mathfrak b= \left( \begin 0 & 1 \\ 1 & 1 \end \right). $$ В этом множестве операцию сложения определим как операцию сложения матриц по модулю $ 2_<> $: $$ \left(\begin a_& a_ \\ a_&a_ \end \right)+ \left(\begin b_& b_ \\ b_&b_ \end \right)= \left(\begin a_+b_ \pmod & a_+b_ \pmod \\ a_+b_ \pmod & a_+b_ \pmod \end \right) $$ а операцию умножения — как операцию умножения матриц, но тоже по модулю $ 2_<> $, т.е.: $$ \left(\begin a_& a_ \\ a_&a_ \end \right)\times \left(\begin b_& b_ \\ b_&b_ \end \right) = \left(\begin a_b_ +a_b_ \pmod & a_b_ +a_b_ \pmod \\ a_b_ +a_b_ \pmod & a_b_ +a_b_ \pmod \end \right) \ . $$ Можно проверить, что таблицы действий с элементами этого множества совпадают с таблицами, приведенными выше. ♦

Пример конечного поля порядка $ p^ $ будет приведен ☟ НИЖЕ. Любое такое поле называется полем Галуа и обозначается 1) $ \mathbf(p^m) $.

Обобщенная теорема Ферма

Теорема. Любой элемент $ \mathfrak a \in \mathbf(p^m) $ удовлетворяет равенству$$ \mathfrak a^ — \mathfrak a = \mathfrak o \ . $$

Доказательство аналогично доказательству малой теоремы Ферма. Обозначим для краткости $ q=p^m $, и рассмотрим все ненулевые элементы поля $$ \mathfrak a_1,\dots, \mathfrak a_ \ . $$ Если $ \mathfrak a \ne \mathfrak o $, то домножим его на все эти элементы: $$ \mathfrak a \mathfrak a_1,\dots, \mathfrak a \mathfrak a_ \ . $$ Получились снова элементы поля. Они все отличны от $ \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 \>_^ $ совпадает со множеством $ \< \mathfrak a_k \>_^ $, но тогда произведения элементов этих множеств одинаковы: $$ \prod_^ (\mathfrak a \mathfrak a_j) = \prod_^ \mathfrak a_j \quad \Rightarrow \quad a^ \prod_^ \mathfrak a_j = \prod_^ \mathfrak a_j \ . $$ Произведение ненулевых элементов поля отлично от $ \mathfrak o $, следовательно $$ \mathfrak a^= \mathfrak e \ ; $$ это равенство справедливо для любого ненулевого элемента поля. Умножив его на $ \mathfrak a $, получим равенство из условия теоремы, которому будет удовлетворять и $ \mathfrak a = \mathfrak o $. ♦

Теорема. Любой элемент $ \mathfrak a \in \mathbf(p^m) $ удовлетворяет равенству

Будем называть выражение вида $$ \mathfrak x^m + A_1 \mathfrak x^ + \dots + A_ = \mathfrak o $$ при $ \ < A_1,\dots,A_m \>\subset \ < \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_\> $ алгебраическим уравнением в $ \mathbf(p^m) $ степени $ m_<> $ относительно неизвестной $ \mathfrak x_<> $.

Доказательство. При доказательстве теоремы 2 из предыдущего пункта было показано, что в любом поле $ \mathbb P $ найдутся $ m_<> $ элементов $ \mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m $ таких, что любой элемент поля можно выразить в виде их линейной комбинации с коэффициентами из множества $ \ < \mathfrak a_\>_^ $. Выразим в виде таких линейных комбинаций элементы $ \mathfrak a, \mathfrak a \mathfrak A_1, \mathfrak a \mathfrak A_2,\dots, \mathfrak a \mathfrak A_m $: $$ \begin \mathfrak a &=& A_ +A_ \mathfrak A_2+\dots+ A_ \mathfrak A_m, \\ \mathfrak a \mathfrak A_2 &=& A_ +A_ \mathfrak A_2+\dots+ A_ \mathfrak A_m, \\ \dots & & \dots \\ \mathfrak a \mathfrak A_m &=& A_ +A_ \mathfrak A_2+\dots+ A_ \mathfrak A_m, \end \qquad npu \quad \ < A_\>_^m \subset \ < \mathfrak a_\>_^ \ . $$ Перепишем эти уравнения: $$ \begin (A_- \mathfrak a) & +A_ \mathfrak A_2 & +\dots & + A_ \mathfrak A_m &=& \mathfrak o, \\ A_ & +(A_- \mathfrak a) \mathfrak A_2 &+\dots & + A_ \mathfrak A_m &=& \mathfrak o, \\ \dots & & & & & \dots \\ A_ & + A_ \mathfrak A_2 & +\dots+ & (A_- \mathfrak a) \mathfrak A_m &=& \mathfrak o. \end $$ Эта система уравнений, рассматриваемая относительно элементов поля $ \mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m $ является линейной и однородной.

В этом месте доказательства мы воспользуемся аналогией задачи с задачей решения системы линейных уравнений с коэффициентами из множества $ \mathbb Z_<> $. Условия разрешимости таких систем могут быть сформулированы в терминах определителей — т.е. полиномиальных функций от коэффициентов системы. Аналог этого объекта для конечного поля очевиден и принципиально вычисляем — поскольку его формальное определение использует только операции сложения и умножения элементов поля. Однако детали этого переноса результатов из бесконечного множества $ \mathbb Z_<> $ в конечное поле $ \mathbb F_<> $ оставляю не освещенными 2) .

Поскольку эта однородная система имеет нетривиальное решение ( $ \mathfrak A_1=\mathfrak e\ne \mathfrak o $), ее определитель должнен быть равен нулевому элементу поля: $$ \left|\begin A_- \mathfrak a & A_ & \dots & A_ \\ A_ & A_- \mathfrak a& \dots & A_ \\ \dots & & & \dots \\ A_ & A_& \dots & A_- \mathfrak a \end \right|= \mathfrak o \ . $$ Определитель в левой части является полиномом от $ \mathfrak a $ степени $ m_<> $ с коэффициентами, которые полиномиально же зависят от величин $ \ < A_\>_^m $, т.е., в конечном итоге, от величин $ \ < \mathfrak a_\>_^ $. ♦

Резюмируем: элемент $ \mathfrak a $ поля $ \mathbf(p^m) $ должен удовлетворять одновременно двум алгебраическим уравнениям в этом поле: $ \mathfrak x^- \mathfrak x = \mathfrak o $ и некоторому уравнению $ \mathfrak x^m + A_1 \mathfrak x^ + \dots + A_ = \mathfrak o $ степени $ m_<> $. Если бы мы имели дело с обычными алгебраическими уравнениями одной переменной с целыми коэффициентами, то мы могли бы сделать заключение о существовании зависимости между коэффициентами этих уравнений в виде некоторого алгебраического равенства (см. ☞ РЕЗУЛЬТАНТ ). В случае же конечного поля, можно вывести более глубокое заключение: второй полином оказывается делителем первого. Осталось только ввести операцию деления полиномов в конечном поле, к чему мы и приступаем.

Пример конечного поля

Полином $ F_<>(x) $ с целыми коэффициентами называется неприводимым по модулю p если его нельзя представить в виде $$ 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) $ приводим по модулю p; в этом случае будем также говорить, что $ F_<>(x) $ делится на $ F_j(x) $ по модулю $ p_<> $, или что $ F_j(x) $ является делителем $ F_<>(x) $ по модулю $ p_<> $.

Очевидно, что если полином $ F(x) \in \mathbb Z[x] $ приводим в $ \mathbb Z_<> $, то он приводим по любому модулю $ p_<> $.

Пример. Приводим ли полином $ 2\,x^2+2\,x+1 $ по модулю $ 5_<> $?

Решение. Этот полином неприводим в $ \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 $$ ♦

Пример. Приводим ли полином $ 2\,x^2+2\,x-1 $ по модулю $ 5_<> $?

Решение. Рассмотрим всевозможные комбинации потенциально возможных линейных множителей с коэффициентами из множества $ \ $: $$ 2\,x\pm 1,\ 2\,x\pm 2,\ x\pm 2,\ x\pm 1 \ . $$ Ни одна пара при перемножении не дает требуемый полином.

Ответ. Нет.

Рассмотрим полином $ f_<>(x) $ степени $ n_<>\ge 1 $ с целыми коэффициентами и нормализованный (т.е. со старшим коэффициентом равным $ 1_<> $): $$ f(x)=x^n+a_1x^+\dots+a_n \in \mathbb Z[x] \ . $$ Доказать, что частное и остаток от деления произвольного полинома $ g_<> (x)\in \mathbb Z[x] $ на $ f_<>(x) $ будут полиномами с целыми коэффициентами.

Подсказка: см. доказательство теоремы ☞ ЗДЕСЬ.

Всюду в этом пункте полином $ f_<> (x) $ предполагается нормализованным и $ \deg f \ge 1 $.

Полиномы $ \ \subset \mathbb Z[x] $ называются сравнимыми по двойному модулю $ p, f(x) $ если их разность может быть представлена в виде $$ F_1(x)-F_2(x) \equiv p\cdot G(x) + f(x) H(x) \quad npu \quad \\subset \mathbb Z[x] \ . $$ Иными словами, остаток от деления $ F_1(x)-F_2(x) $ на $ f_<>(x) $ представляет собой полином, все коэффициенты которого кратны $ p_<> $: $$ \left( F_1(x)-F_2(x) \pmod \right) \pmod

\equiv 0 \ ; $$ здесь знак $ \equiv_<> $ обозначает тождественное равенство. В [1] для этого понятия используется обозначение $$ F_1(x)\equiv F_2(x) \quad (\operatorname \ p,f(x)) \ , $$ на мой взгяд, очень наглядное. Однако ни в каком другом источнике я его не встречал.

Пример. Найти все значения параметра $ \alpha \in \mathbb Z $, при которых полиномы

$$ 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 $.

Решение. Делим $ 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_<> $ только при условии

Ответ. $ \alpha \equiv 1 \pmod 5 $.

Будем использовать обозначение $$ F(x)= F_1(x) \quad (\operatorname \ p,f(x)) $$ в том же смысле, что в разделе ☞ МОДУЛЯРНАЯ АРИФМЕТИКА использовалось обозначение $ x = A \pmod $, т.е. полиному $ F_<>(x) $ присваивается значение остатка от деления $ F_1(x) $ на $ f_<>(x) $, в котором дополнительно производится усечение каждого коэффициента до его остатка от деления на $ 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 \ 7,f(x)) \ . $$

Теорема. Пусть $ f_<>(x) $ — нормализованный неприводимый по модулю $ p_<> $ полином степени $ m\ge 1 $. Множество полиномов

$$ \mathbb P_ = \< F (x)=A_0+A_1x+\dots+A_x^ \ \mid \ \ \subset \ \> \ , $$ рассматриваемое относительно операции сложения по модулю $ p_<> $: $$ F_1(x)+F_2(x) \pmod

$$ и операции умножения по двойному модулю $ p, f(x) $: $$ F_1(x) F_2(x) \quad (\operatorname \ p,f(x)) $$ образует поле Галуа $ \mathbf(p^m) $.

Доказательство. Все элементы множества $ \mathbb P_ $ различны, поскольку каждый определяется набором своих коэффициентов $ (A_0,A_1,\dots,A_) $ однозначно. Каждый из коэффициентов, независимо от других, может принимать $ p_<> $ различных значений, следовательно $ \operatorname ( \mathbb P_ ) = p^m $.

Введенные во множестве $ \mathbb P_ $ операции удовлетворяют аксиомам 1 — 8 поля; сложность вызовет лишь проверка аксиомы 8 о существовании полинома, обратного произвольному полиному $ F(x) \in \mathbb P_, F(x) \not\equiv 0 $ относительно умножения по двойному модулю $ p,f(x) $. Требуется удостовериться, что существует полином $ U(x) \in \mathbb P_ $ такой, что $$ U(x)F(x) \quad (\operatorname \ p,f(x)) \equiv 1 \ . $$

Если $ F_<>(x) $ тождественно равен константе $ F(x)\equiv A_0 $, то искомый полином $ U(x) $ тоже будет константой: $ U(x)\equiv U_0 $, где $ U_0A_0 \equiv 1 \pmod

$. Последнее сравнение имеет решение для любого $ A_0\in \ $, это решение будет единственны в том же множестве, и оно называется мультипликативным обратным числу $ A_0 $ по модулю $ p_<> $. Соответствующую теорию и сопутствующие алгоритмы нахождения см. ☞ ЗДЕСЬ; сугубо же для теоретических манипуляций нам достаточно будет его представления посредством малой теоремы Ферма: $$ A_0^= A^ \pmod

\ . $$

Предположим теперь, что $ F(x) \not\equiv const $: $$ F(x) = A_0+A_1x+\dots+A_x^ \quad npu \quad A_ \ne 0, \ell > 0 \ . $$

Вся оставшаяся часть доказательства представляет собой, фактически, алгоритм Евклида нахождения наибольшего общего делителя полиномов $ f_<>(x) $ и $ F_<>(x) $ — вместе с нахождением его линейного представления. Отличие от классического алгоритма Евклида будет заключаться в том, что по выполнении каждого деления целочисленных полиномов, мы будем избавляться от появляющихся в выражениях частных и остатков знаменателей дробей (сохраняя целочисленность полиномов). Такая операция оказывается возможной за счет того, что во множестве $ \ $ можно организовать операцию деления, которая не выведет за пределы этого множества — если операция умножения этих чисел вводится по модулю простого числа $ 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_$: $ \< 1,A_,\dots, A_^ \> $. Заменим каждое рациональное число вида $$ \frac $$ на $$ B A_^ \pmod

; $$ на основании малой теоремы Ферма, числа $ A_^K $ и $ A_^ $ являются мультипликативными обратными относительно умножения по модулю $ p_<> $: $$A_^\cdot A_^K \equiv 1 \pmod

\ . $$ Произведя все подобные замены в последнем полиномиальном тождестве, получим его целочисленный вариант $$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 \ $. Домножим тождество $$f(x)\equiv Q_1(x)F(x)+ C_0 $$ на мультипликативное обратное числу $ C_0 $ по модулю $ p_<> $, представив его, например, в виде $ C_0^ \pmod

$. Получим $$ C_0^ f(x) — C_0^Q_1(x)F(x) \equiv 1 \pmod

\ . $$ Из последнего тождества тогда следует, что в качестве полинома $ U(x) $, удовлетворяющего $$ U(x)F(x) \quad (\operatorname \ p,f(x)) \equiv 1 \ , $$ можно взять $ [- C_0^Q_1(x)] \pmod

$.

Идем далее. Предположим, что полином $ 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 $. Если полином $ 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^ \pmod

$. Получим $$ D_0^ F(x) — D_0^Q_2(x)R_1(x) \equiv 1 \pmod

\ . $$ Подставим в это тождество представление для $ R_1(x) $ из его определения в предыдущем абзаце: $$ R_1(x) \equiv f(x)- Q_1(x)F(x), $$ приходим к тождеству $$D_0^ (Q_1(x)Q_2(x)+1)F(x)-D_0^Q_2(x)f(x) \equiv 1 . $$ Из него следует, что в качестве полинома $ U(x) $, удовлетворяющего $$ U(x)F(x) \quad (\operatorname \ p,f(x)) \equiv 1 \ , $$ можно взять $ D_0^ (Q_1(x)Q_2(x)+1) \pmod

$.

Наконец, если полином $ 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 $-м шаге: $$R_(x)\equiv Q_k(x) R_(x)+ R_k $$ и $ R_k \not\equiv 0 \pmod

$. Умножив тождество на $ R_k^ $ приведем его к виду $$1\equiv R_k^ R_(x)- R_k^ Q_k(x) R_(x) \ . $$ Далее возвращаемся назад в алгоритме последовательного деления. Из предпоследнего шага можно выразить $ R_(x) $ через $ R_ (x) $ и $ R_ (x) $, подставив их выражения в последнее тождество, получим $$1\equiv R_k^[1+Q_k(x)Q_(x)] R_(x)- R_k^ Q_k(x) R_(x) \ . $$ Возвращаемся еще на один шаг назад, выражаем правую часть последнего тождества через предшествующие остатки, и т.д. В конце концов, придем к представлению $$1 \equiv V(x)f(x)+U(x)F(x) \ . $$ Но оно эквивалентно искомому $$ U(x)F(x) \quad (\operatorname \ p,f(x)) \equiv 1 \ . $$ ♦

Практическое нахождение элемента, обратного в поле Галуа заданному, возможно разными способами. Все они, прямо или опосредовано, завязаны на полиномиальное тождество, известное под названием тождества Безу: это тождество имеет вид $$ v(x)f(x)+u(x)g(x)\equiv 1 \ . $$ При фиксированных полиномах $ f_<>(x) $ и $ g_<>(x) $ его выполнимость (хотя бы при одной паре полиномов $ u(x) $ и $ v(x) $) имеет место тогда и только тогда, когда $ f_<>(x) $ и $ g_<>(x) $ взаимно просты: $ \operatorname(f,g) \equiv 1 $. Способы решения этого тождества в бесконечных полях посредством вычисления континуанты изложены в ☞ ПУНКТЕ; менее практичен, но более нагляден способ, основанный на представлении результанта полиномов $ f_<>(x) $ и $ g_<>(x) $ в виде подходящего определителя, составленного из коэффициентов этих полиномов: см. ☞ ЗДЕСЬ. Можно воспользоваться любым из этих способов для получения промежуточного результата в задаче обращения элемента в поле Галуа: для полиномов $ f_<>(x) $ и $ F_<>(x) $ с целочисленными коэффициентами, сначала получить представления полиномов $ v(x) $ и $ u(x) $ с коэффициентами рациональными, а затем избавиться от знаменателей дробей переходом к обратным по модулю $ p_<> $. Проиллюстрируем эту идею на примере.

Пример. В поле $ \mathbf(7^5) $, порожденном полиномов $ f(x)=x^5+3\,x+1 $, найти элемент обратный $ 2\,x^4+3\,x^3+4\,x+1 $.

Решение. Тождество Безу $$ v(x)f(x)+u(x)F(x)\equiv 1 \ . $$ будет иметь место при 4) $$ u(x)=-\frac-\fracx-\fracx^2+\fracx^3-\fracx^4, \quad v(x)\equiv \dots $$ Далее, решаем сравнения $$ 650\,z_1 \equiv 1,\ 1300 \,z_2 \equiv 1,\ 325 \, z_3 \equiv 1 \pmod $$ получаем мультипликативные обратные к знаменателям $ z_1=6,z_2=3,z_3=5 \pmod $. Избавляемся от знаменателей в коэффициентах полинома $ 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_ \dots $$

Ответ. $ (2\,x^4+3\,x^3+4\,x+1)^ \quad (\operatorname \ 7,x^5+3\,x+1) = 4\,x^4+4\,x^3+2\,x^2+6\,x $.

Строгое — с формальной точки зрения — введение объекта $ \mathbb P_ $ предыдущей теоремы должно было производиться на основе классов вычетов по модулю $ p_<> $: $$ \mathbb P_ = $$ $$ = \< F (x)=A_0+A_1x+\dots+A_x^ \ \mid \ \ \subset \ <\overline 0, \overline 1,\dots, \overline\> \> \ . $$ Я пренебрег строгостью в ущерб наглядности. Из этих же соображений 5) часто ниже буду использовать тот же объект в варианте $$ \mathbb P_ = $$ $$=\left\< \begin F (x)=\sum_^ A_x^ & \ \subset \\ & \subset \left\, -\frac+1,\dots,-1, 0, 1, 2,\dots, \frac \right\> \end \right\> , $$ для нечетных простых чисел $ p_<> $. Иногда этот вариант более удобен по сравнению с использованным в теореме — хотя бы потому, что коэффициенты полиномов $ F(x) $ уменьшаются по абсолютной величине.

Пример. Построить поле $ \mathbf(4) $.

Решение. Здесь $ p=2 $ и $ m_<>=2 $. Полином $ f(x)=x^2+x+1 $ является неприводимым по модулю $ 2_<> $. Согласно теореме, множество из четырех полиномов $ \ $ с операцией сложения по модулю $ 2_<> $ и операцией умножения по двойному модулю $ 2, x^2+x+1 $ образует поле. Результаты операций, собранные в таблицы $$ \begin \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 \qquad \qquad \begin \mathbb & 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 $$ полностью соответствуют приведенным в начале раздела, где выводились правила действий в произвольном поле $ \mathbf(4) $. Иными словами, существует изоморфизм между произвольным полем $ \mathbf(4) $ (например полем из четырех матриц, построенным в конце ☞ ПУНКТА ) и полем из полиномов, построенным в настоящем примере. ♦

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

Доказательства этой теоремы, приведенные в литературе, оказались трудны для моего понимания, поэтому я просто привожу проверку этого утверждения на примере ☞ ЗДЕСЬ.

Полиномы, неприводимые по модулю

В настоящем пункте под неприводимым полиномом понимается нормализованный неприводимый полином.

Теорема 1. Любой неприводимый по модулю $ p_<> $ полином степени $ n_<> $ является делителем полинома $ x^- x $ (по модулю $ p_<> $).

Доказательство. В предыдущем пункте было доказано, что если $ f_<>(x) $ неприводимый по модулю $ p_<> $ полином степени $ n_<> $, то множество $ \mathbb P_ $ полиномов степеней $ < n $ с коэффициентами из $ \$ образует поле Галуа $ \mathbf (p^n) $ относительно введенных операций сложения по модулю $ p_<> $ и умножения по двойному модулю $ p,f(x) $. Но тогда любой полином $ F(x) \in \mathbb P_ $ должен удовлетворять обобщенной теореме Ферма: $$ \left[F(x)\right]^ — F(x) \equiv 0 \quad (\operatorname \ p,f(x)) \ . $$ В частности, это должно быть справедливо и для $ F(x) \equiv x $. Тогда полином $$ x^-x $$ должен делиться на полином $ f_<> (x) $ по модулю $ p_<> $. ♦

Полученное в ходе доказательства утверждение о том, что любой полином $ F(x) \in \mathbb P_ $ должен обладать свойством $ \left[F(x)\right]^ — F(x) \equiv 0 \quad (\operatorname \ p,f(x)) $ хочется проверить косвенным образом. Покажем, что оно является прямым следствием сравнения $ x^ — x \equiv 0 \quad (\operatorname \ p,f(x)) $ ☞ ЗДЕСЬ.

Таким образом, чтобы найти все неприводимые по модулю $ p_<> $ полиномы степени $ n_<> $ следует разложить полином $ x^- x $ на неприводимые по модулю $ p_<> $ множители. При этом часть множителей может иметь степень $ < n_<>$. Однако, существование для любых $ p_<> $ и $ n_<> $ неприводимых по модулю $ p_<> $ полиномов степени $ n_<> $ еще требует доказательства.

Теорема 2. Если элемент $ \mathfrak a \in \mathbf (p^m) $ удовлетворяет неприводимому уравнению степени $ n_<> $, то равенство $ \mathfrak a^ — \mathfrak a = \mathfrak o $ возможно тогда и только тогда, когда $ m_<> $ делится на $ n_<> $.

Доказательство ☞ ЗДЕСЬ.

Теорема 3. Полином $ x^- x $ разлагается по модулю $ p_<> $ на неприводимые полиномы, степени которых равны или $ m_<> $ или делителям $ m_<> $.

Непосредственным следствием теоремы 2 является

Теорема 4. Обозначим через 6) $ \xi_p (k) $ число неприводимых по модулю $ p_<> $ полиномов степени $ k_<> $. Имеет место равенство

$$ p^m=\sum_ k \xi_p (k) \ ; $$ здесь суммирование производится по всем индексам $ k_<> $ , являющимися делителями числа $ m_<> $.

Определить $ \xi_p (m) $ для случая простого $ m_<> $. Установить для этого случая асимптотику $ \xi_p (m)/p^m $ при $ m \to \infty $.

Если в каноническом разложении числа $ m_<> $ на множители содержатся только различные простые числа, то имеет место равенство:

$$ \xi_p (m) =\frac \left(p^m- \sum_ p^>+\sum_,k_> p^k_)>- \sum_,k_,k_> p^k_k_)> + \dots \right) \ , $$ где $ k_1,k_2,k_3,\dots $ пробегают всевозможные делители числа $ m_<> $.

Пример. Определить $ \xi_p (30) $.

Решение. Поскольку $ 30=2\cdot 3 \cdot 5 $, то имеем: $$ \xi_p (30) = \frac \left(p^-p^-p^-p^6+p^5+p^3+p^2-p \right) \ . $$ Так, $ \xi_2 (30)= 35790267,\ \xi_3 (30) =6863037256208 $. ♦

В поле Галуа первообразным корнем степени n из единицы называется элемент $ \mathfrak a $, который удовлетворяет условиям $$ \mathfrak a^n=\mathfrak e \ , \mathfrak a^k \ne \mathfrak e \quad npu \quad k\in \ \ . $$ Будем также говорить, что $ \mathfrak a $ принадлежит показателю n или, что $ \mathfrak a $ имеет порядок n.

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

Теорема 5. В поле Галуа $ \mathbf (p^m) $ существуют первообразные корни степени $ p^m-1 $ из единицы.

Доказательство (и критерий, часто позволяющий быстро отыскать такие корни) ☞ ЗДЕСЬ.

В поле $ \mathbf (p^m) $ первообразный корень степени $ p^m-1 $ из единицы называется примитивным элементом поля.

Количество примитивных элементов поля $ \mathbf (p^m) $ равно $ \phi(p^m-1) $, где $ \phi $ — функция Эйлера.

В любом поле Галуа группа относительно умножения — циклическая, иными словами: все ненулевые элементы поля $ \mathbf (p^m) $ находятся во множестве $ \ < \mathfrak A^0,\mathfrak A^1,\dots,\mathfrak A^\> $ при выборе в качестве $ \mathfrak A $ произвольного примитивного элемента.

Пример 1. Пусть $ p=3, m=2 $. Выбрав в качестве неприводимого по модулю $ 3_<> $ полинома 7)

$$ f(x)=x^2-x-1 \, ,$$ получим, что элементами поля $ \mathbf (3^2) $ должны быть полиномы степени не выше $ 1_<> $ с коэффициентами из множества $ \ $. Возьмем в качестве примитивного элемента поля полином тождественно равный 8) $ x_<> $. Получим, последовательным возведением его в степень: $$ x^0\equiv 1,\ x^1\equiv x,\ x^2 \equiv x+1 \quad (\operatorname \ 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 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 $$ Цикл завершен. ♦

Теорема 6. Полином $ x^- x $ содержит неприводимые по модулю $ p_<> $ сомножители степени $ m_<> $.

Доказательство. Если бы первообразный корень $ \mathfrak a $ степени $ p^m -1 $ из единицы удовлетворял бы уравнению степени $ n — \mathfrak e = \mathfrak o $, что, ввиду неравенства $ p^n-1 < p^m-1 $ невозможно. ♦

Пример 2. Разложить полином $ x^-x $ на неприводимые по модулю $ 2_<> $ множители.

Решение. Воспользуемся результатом из пункта УРАВНЕНИЕ ДЕЛЕНИЯ КРУГА. $$ x^-x \equiv x \left(x^-1 \right) \equiv x\, X_1(x)X_3(x)X_5(x)X_(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 16 & = & 4 \xi (4) & + 2\xi (2) & + \xi (1), \\ 4 & = & & 2\xi (2) & + \xi (1), \\ 2 & = & & & \xi (1), \end $$ откуда: $ \xi (1)=2, \xi (2)=1, \xi (4)=3 $. Таким образом, получаем что по модулю $ 2_<> $ имеется (в-точности) $ 2_<> $ неприводимых линейных полинома, оба уже наблюдаются в разложении: $$ x \quad \mbox < и >\quad x-1 \equiv x+1 \pmod \ ; $$ Неприводимый полином $ 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 \ . $$ ♦

Пример 3. Найти все неприводимые по модулю $ 2_<> $ полиномы $ 3_<> $-й степени.

Решение. Для получения этих полиномов — в соответствии с теоремой 3 — надо разложить на множители полином $ x^-x $. Имеем $$ x^-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 4 & = & 3\xi (3) & + \xi (1), \\ 2 & = & & \xi (1), \end $$ откуда $ \xi (3)=2 $. ♦

Пример 4. Разложить полином $ x^-x $ на неприводимые по модулю $ 3_<> $ множители.

Полиномы над GF(2)

Наибольшую важность для приложений в теории кодирования имеют поля $ \mathbf(2^m) $. Рассмотрим примеры полей из полиномов с коэффициентами из множества $ \ $ — о таких полиномах часто говорят как о полиномах над GF(2). На этих примерах мы проиллюстрируем еще раз результаты предыдущих пунктов.

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

Доказать, что любой неприводимый по модулю $ 2_<> $ полином степени $ n> 1 $ имеет нечетное число мономов.

Пример. Исследовать поле $ \mathbf(16) $.

Решение. Поле содержит $ 16_<> $ элементов: полиномов вида $ A_0x^3+A_1x^2+A_2x+A_3 $ при $ \ \in \ $. Теперь надо определить операцию умножения. Разложение полинома $ x^-x $ на неприводимые по модулю $ 2_<> $ множители приведено в предыдущем пункте: $$ x^-x \equiv_> 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 $. Следующая таблица выражает все полиномы из поля через посредство выражений для степеней $ \ \quad (\operatorname \ 2,f(x)) \>_^ $: $$ \begin 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^ & & x^2 &+x & +1 & 0111 \\ x^ & x^3 & +x^2 & +x & & 1110 & \Pi \\ \hline x^ & x^3 & +x^2 & + x& +1 & 1111 \\ x^ & x^3 & +x^2 & & +1 & 1101 & \Pi \\ x^ & x^3 & & & +1 & 1001 & \Pi \end $$ (и если бы мы продолжили эту таблицу, то следующим шагом вышли бы на цикл: $ x^ \quad (\operatorname \ 2,f(x)) \equiv 1 $). В третьем столбце стоят двоичные наборы коэффициентов полиномов, рассматриваемых в разложении по убывающим степеням $ x_<> $. В четвертом столбце отмечены примитивные элементы поля, т.е. элементы, степени которых порождают все ненулевые элементы поля (одним из них являлся полином, тождественно равный $ x_<> $, по которому, собственно, и составлена таблица; с тем же успехом мы могли бы рассматривать и $ \ <\left(x^2\right)^k \quad (\operatorname\ 2,f(x)) \>_^ $ или $ \<\left(x^\right)^k \quad (\operatorname \ 2,f(x)) \>_^ $, и т.п.). Количество примитивных элементов равно $ \phi(2^4-1)=\phi(15)=8 $. Все они обязаны удовлетворять алгебраическим уравнениям, степеней равных делителям числа $ 16_<> $. Все эти уравнения можно получить из разложения полинома $ x^ — 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 (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^+1)^4+(x^2+1)+1 \equiv x^2+(x^2+1)+1 \equiv 0 \ . \end $$ Оставшиеся $ 4_<> $ примитивных элемента поля, именно, $ x^7,x^,x^,x^ $ должны удовлетворять другому уравнению $ 4_<> $-й степени, которое соответствует одному из оставшихся неприводимых полиномов этой степени. В самом деле, они удовлетворяют уравнению $ \mathfrak x^4+\mathfrak x^3+\mathfrak e= \mathfrak o $: $$ (x^7)^4 + (x^7)^3+1 \equiv x^+x^+1 \equiv x^+x^+1\equiv x^3+x^2+1+(x^3+x^2)+1 \equiv 0 \ . $$ Последние вычисления проводились с учетом $ x^ \equiv 1 $ и с использованием построенной выше таблицы для степеней $ x^ $.

Примитивные элементы поля, т.е. элементы порядка $ 15_<> $, исчерпаны. Все остальные элементы поля имеют порядки, равные $ 1_<>, 3_<> $ или $ 5_<> $, т.е. — в соответствии с теоремой предыдущего пункта — делителям числа $ 15_<> $. Рассмотрим последовательность $ \ <\left(x^3\right)^k \quad (\operatorname\ 2,f(x)) \>_^ $: $$ (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^ \equiv x^3 +x^2+x+1,\ (x^3)^5 \equiv x^ \equiv 1 \ . $$ Итак, элемент поля $ x^ $ принадлежит показателю $ 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^-x $. На всякий случай, осуществим выборочную проверку: $$ (x^9)^4+(x^9)^3+(x^9)^2+x^9+1 \equiv x^+x^+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^ $. Они должны принадлежать показателю $ 3_<> $, что и немедленно проверяется. Кроме того, они должны удовлетворять неприводимому уравнению из разложения $ x^-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_<> $ — с ними все просто. ♦

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

Для предыдущего примера составить аналоги таблицы степеней $ \ <\mathfrak a^\quad (\operatorname \ 2,f(x)) \>_^ $ при выборе в качестве $ f_<>(x) $
а) $ x^4+x^3+1 $; б) $ x^4+x^3+x^2+x+1 $; а также подходящего примитивного элемента $ \mathfrak a $.

Решение ☞ ЗДЕСЬ.

Теперь займемся неприводимыми полиномами. Сначала оценим их число — в абсолютном количестве, а также в отношении к общему количеству полиномов степени $ k_<> $: $$ \begin 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 $$

Разложить полином $ x^-x $ на неприводимые по модулю $ 2_<> $ множители.

Решение ☞ ЗДЕСЬ.

Полиномы над GF(p)

Теперь обобщим результаты разобранных в предыдущем пункте примеров. Будем рассматривать полиномы $ F_<>(x) $ над $ \mathbf(p) $. Нас будут интересовать решения уравнения $$ F(\mathfrak x) \equiv \mathfrak o \ . $$ среди элементов конечного поля $ \mathbf(p^m) $. Любой такой элемент $ \mathfrak a $ будем называть корнем полинома $ F_<> $ в поле $ \mathbf(p^m) $.

Теорема 1. Пусть $ F_<>(x) $ — неприводимый по модулю $ p_<> $ полином степени $ n_<> $ и $ \mathfrak a \in \mathbf(p^m) $ — его корень. Тогда множество корней $ F_<>(x) $ в поле $ \mathbf(p^m) $ совпадает с $$ \mathfrak a, \mathfrak a^p, \mathfrak a^,\dots, \mathfrak a^> \ . $$

Доказательство. Воспользуемся теоремой Шёнеманна: для произвольного полинома $ F(x)\in \mathbb Z[x] $ выполняется $$ \left[F(x)\right]^p \equiv F(x^p) \pmod

\ . $$ Тогда если $ F(\mathfrak a)= \mathfrak o $, то и $ F(\mathfrak a^p)= \mathfrak o $, но тогда и $ F((\mathfrak a^p)^p)= \mathfrak o $, и т.д. С другой стороны, все элементы множества $ \ < \mathfrak a^\>_^ $ различны. Действительно, если бы выполнялось равенство $$ \mathfrak a^=\mathfrak a^ \qquad npu \qquad 0\le j < k \le n-1 \ , $$ то возведением его в степень $ p^$, получим равенство $$ \mathfrak a^>=\mathfrak a^ = \mathfrak a \ . $$ Последнее равенство следует из доказательства теоремы из ☞ ПУНКТА. Однако равенство $$ \mathfrak a^>= \mathfrak a $$ невозможно, поскольку $ n+j-k< n $, а, ввиду теоремы 3 из ☞ ПУНКТА, полином $ x^>-x $ делится лишь на такие неприводимые по модулю $ p_<> $ полиномы, степени которых являются делителями числа $ n+j-k $ и, следовательно, не может делиться на $ F_<>(x) $. ♦

Теорема 2. Все корни неприводимого полинома $ F_<>(x) $ принадлежат одному показателю (имеют одинаковый порядок).

Показатель корней неприводимого полинома называется показателем, которому этот полином принадлежит. Если неприводимый полином $ F_<>(x) $ принадлежит показателю $ \ell_<> $, то он является делителем полинома $ x^-1 $, но не является делителем ни одного из полиномов $ x^k-1 $ при $ k\in \ $. Неприводимый полином степени $ m_<> $ над $ \mathbf(p) $ называется примитивным, если его корнем является примитивный элемент поля $ \mathbf(p^m) $. В этом случае, этот корень принадлежит показателю $ p^m-1 $, и по теореме 2, все корни $ F_<>(x) $ принадлежат тому же показателю, т.е. являются примитивными элементами поля.

Число неприводимых полиномов степени $ m_<>>1 $ равно $ \phi (p^m-1)/m $.

Получается, что число $ \phi (p^m-1) $ должно делиться нацело на $ m_<> $. Результат, который вовсе не очевиден из элементарных соображений. Тем не менее, он верен даже для случая когда вместо $ p_<> $ рассматривается составное число; см. следствие к теореме 3 ☞ ЗДЕСЬ.

Неприводимый полином $ F_<>(x) $ степени $ m_<> $ является примитивным тогда и только тогда, когда он не является делителем ни одного из полиномов $ x^k-1 $ при $ k\in \ $. Если каноническое разложение числа $ p^m-1 $ имеет вид:

$$ p^m-1=p_1^<<\mathfrak m>_>p_2^<<\mathfrak m>_>\times \dots \times p_<\mathfrak r>^<<\mathfrak m>_<_<\mathfrak r>>> \ , $$ то для того чтобы неприводимый полином $ F_<>(x) $ степени $ m_<> $ был примитивным, необходимо и достаточно, чтобы он не являлся делителем ни одного из полиномов $ x^-1 $ при $ \forall j \in \ $.

Пример. Из трех неприводимых полиномов $ 4_<> $-й степени:

$$ x^4+x+1, \ x^4+x^3+1, \ x^4+x^3+x^2+x+1 $$ примитивными будут только первый и второй. Подробный разбор см. ☞ ЗДЕСЬ.

Пример. Примитивные полиномы $ 6_<> $-й степени см. ☞ ЗДЕСЬ.

Источники

[1]. Чеботарев Н. Основы теории Галуа. Часть I. М.-Л.ОНТИ. 1934.

[2]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.

[3]. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.Мир. 1988.

[4]. Ротман Т. Короткая жизнь Эвариста Галуа. Scientific American. N 1, 1983, cc. 84-93. Текст ☞ ЗДЕСЬ.

Galois field
Как они не освещены и в [1], откуда я этот результат взял.
Все тождества далее — если не обговорено особо — рассматриваются по модулю $ p_<> $.
Выражение для $ v_<>(x) $ нас совершенно не интересует.
и без дополнительных предупреждений

Иногда будем использовать это обозначение без индекса, если по контексту понятно о каком модуле $ p_<> $ идет речь.

См. пример 4 ниже.

Заметим, что выбор примитивного элемента поля не всегда тривиален, и не всегда в качестве этого элемента можно взять $ x_<> $; но, по крайней мере, проверить конкретный элемент на примитивность принципиально возможно — см. теорему 2 ☞ ЗДЕСЬ.

Конечное поле

Коне́чное по́ле, или по́ле Галуа́ в общей алгебре — поле, состоящее из конечного числа элементов. Число элементов в поле называется его поря́дком.

Наиболее известным примером конечного поля является поле классов вычетов по простому модулю, то есть факторкольцо — простое число [1] .

Конечное поле обычно обозначается (q)» /> (сокращение от Galois field) и называется полем Галуа порядка [2] , где — число элементов поля. С точностью до изоморфизма конечное поле полностью определяется его порядком, который всегда является степенью какого-нибудь простого числа, то есть , где — простое число, а — любое натуральное число. При этом будет являтся характеристикой этого поля [3] .

Определение [ править ]

Конечным полем называется конечный набор элементов, на котором определены операции сложения, умножения, вычитания и деления (кроме деления на 0), удовлетворяющие аксиомам поля [7] .

Поле с простым числом элементов и связь с кольцами вычетов [ править ]

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

Любое поле простого порядка может быть представлено кольцом вычетов (т.е. любое поле из элементов изоморфно полю является полем. Кольцо является полем тогда и только тогда, когда — простое число [9] . Если же — составное число, то не все ненулевые элементы кольца обратимы. Например, — не поле, так как элемент в этом кольце не обратим. Тем не менее, существует поле, состоящее из четырёх элементов (см. ниже).

Характеризация конечных полей [ править ]

Характеристика каждого конечного поля является простым числом. Пусть — конечное поле. Тогда оно состоит из элементов, где — характеристика поля , а натуральное число — степень поля над его простым подполем [3] .

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

Построение [ править ]

Поле =\mathbb F_p[x]/(f(x))» />, где — неприводимый многочлен степени n над полем . Таким образом, для построения поля из элементов достаточно отыскать многочлен степени , неприводимый над полем . Элементами поля с коэффициентами из по модулю главного идеала, порождённого многочленом .

Элемент и поле _p» />, поэтому переход от поля _p[x]/(f(x))» /> называется присоединением к полю . [11] [12]

Свойства [ править ]

Цикличность мультипликативной группы [ править ]

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

Порождающий элемент называется также примитивным элементом поля Поле содержит примитивных элементов, где — функция Эйлера. [13]

Другие свойства [ править ]

• Каждый элемент поля [3] .
• Поле _» /> тогда и только тогда, когда является делителем [2] .
• Если — неприводимый многочлен степени , то поле , причём множество всех его корней имеет вид » /> является полем разложения многочлена над полем [14] .
• Для каждого конечного поля и натурального числа произведение всех нормированных неприводимых над многочленов, степень которых делит , равно [15] .
• Число нормированных многочленов степени n, неприводимых над полем \sum_ \mu(d)q^<\frac>» />, где — функция Мёбиуса. Это утверждение следует из формулы

  Поле _2″ /> состоит из двух элементов, но оно может быть задано разными способами в зависимости от выбора элементов и определения операций сложения и умножения на них: [17]

  • Как множество из двух чисел «0» и «1», на котором операции сложения и умножения определены как сложение и умножение чисел с приведением результата по модулю 2:

  +	0	1
  0	0	1
  1	1	0

  ×	0	1
  0	0	0
  1	0	1

  Поле Галуа. Свойства конечных полей.

  Конечное поле (поле Галуа) – конечное множество с двумя определенными на нем операциями, сложения и умножения, в котором определены правила для выполнения арифметических операций, содержащее q элементов и обозначаемое GF(q).

  Свойства конечного поля:

  1. Может образовывать абелевую группу по сложению.

  2. Поле замкнуто относительно умножения и множество не нулевых элементов образует

  абелевую группу по умножению.

  3. Выполняется правило ассоциативности, коммутативности и дистрибутивности для любого

  4. Поле всегда содержит мультипликативную единицу и аддитивную единицу, для любого

  5. Для любого элемента поля существует обратный элемент по сложению и обратный элемент

  Конечное поле существует в случае, если число элементов поля является простым числом или степенью простого числа.

  Наименьшее поле является двоичным полем, т.е. q = 2 и содержит элементы 0, 1:

  Для выполнения вычитания или деления необходимо найти соответственный обратный элемент, а

  затем выполнить сложение или умножение. Например:

  Для сложения и умножения обратный элемент находить не требуется.

  Поле обладает всеми свойствами кольца, а так же обладает следующим свойством: в поле всегда возможно сокращение, представляющее собой некоторую форму деления и означает, что если a*b=c*b=,то a=c.

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

  т.к. =2, =4, =3, =1 (mod 5) т.к. =3, =2, =6, =4, =5, =1 (mod 7)

  Требуется определить все элементы, входящие в GF(5), и представить таблицы сложения и умножения в данном поле.

  

  Расширенное поле Галуа. Вычисления в конечных полях.

  Расширенное поле Галуа (GF( )) – конечное множество, которое образуется как система вычетов по двойному модулю f (x),p и элементами такого поля являются полиномы степени не выше n −1 и с коэффициентами GF(p).

  Неравномерные эффективные коды. Проблема декодирования. Вектор Крафта.

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

  Методы эффективного кодирования основаны на принципах:

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

  Проблема декодирования неравномерного кода:

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

  Вектор (L₁, L_2,…, L_k) состоит из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него выполняется неравенство – неравенство Крафта: