УказательРазделыОбозначенияАвторО проекте


{}_{.} Настоящий раздел поддерживается компанией


!

25 октября 2011 г. исполнилось 200 лет со дня рождения Эвариста Галуа. Почтите его память хотя бы чтением его биографии [4].


!

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


Поля Галуа

§

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

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

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

П

Пример. Множество \mathbb Z_{p} классов вычетов по простому модулю p_{} образует поле относительно операций сложения и умножения.

Рассмотрим теперь конечные поля самого общего вида. Любое такое поле \mathbb F_{} должно содержать нейтральный элементы относительно сложения и умножения: \mathfrak o — нулевой и \mathfrak e — единичный. Начнем последовательно складывать единичные элементы

\mathfrak a_1= \mathfrak e,\ \mathfrak a_2=\mathfrak e+\mathfrak e,\ \mathfrak a_3=\mathfrak e+\mathfrak e+\mathfrak e,\dots

Поскольку, по предположению, поле содержит лишь конечное число элементов, то элементы последовательности \{\mathfrak a_j\}_{j\in \mathbb N} должны повторяться. Если \mathfrak a_k= \mathfrak a_{\ell} при k<\ell, то

\mathfrak a_{\ell-k}= \mathfrak a_{\ell}-\mathfrak a_k = \mathfrak o \ .

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

Т

Теорема 1. Пусть первый нулевой элемент последовательности \{\mathfrak a_j\} имеет номер M_{}:

\mathfrak a_M=\mathfrak o, \mathfrak a_j \ne \mathfrak o \quad npu \quad j\in \{1,\dots,M-1\} .

Число M_{}простое. Все элементы \mathfrak a_1,\dots,\mathfrak a_{M-1} различны.

Доказательство. Если M_{} — составное: M=M_1M_2 при M_1<M и M_2<M, то

\mathfrak o=\mathfrak a_M=\mathfrak a_{M_1}\cdot \mathfrak a_{M_2} \ .

Оба элемента \mathfrak a_{M_1} и \mathfrak a_{M_2} по предположению, ненулевые, а их произведение — нулевой элемент. Но это противоречит свойству поля. Оставшееся утверждение теоремы докажите самостоятельно.

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

Т

Теорема 2. Порядок (число элементов) любого конечного поля равен некоторой степени его характеристики:

\operatorname{Card} (\mathbb F) = p^m \quad при \quad p - простом и \quad m \in \mathbb N \ .

Доказательство. В предыдущей теореме было доказано, что конечное поле \mathbb F характеристики p_{} содержит p_{} различных элементов:

\mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_{p-1} \quad npu \quad \mathfrak a_j= \underbrace{\mathfrak e + \dots+ \mathfrak e}_{j} \ .

Это множество обладает всеми свойствами поля и изоморфно полю \mathbb Z_p. Изоморфизм устанавливается соответствием \mathfrak a_j \mapsto \overline j. Действительно, по предположению \mathfrak a_p= \mathfrak o, но тогда

\mathfrak a_{p+1}= \mathfrak a_1, \mathfrak a_{p+2}= \mathfrak a_2, \dots , \mathfrak a_{p+j}= \mathfrak a_j, \dots ,

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

\mathfrak a_j \cdot \mathfrak a_k=\mathfrak a_{jk} = \mathfrak a_{jk \pmod{p}} \ ,

т.е. \mathfrak a_j \cdot \mathfrak a_k \mapsto \overline{jk}.

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

Если в поле \mathbb F нет других элементов, то \mathbb F = \{ \mathfrak a_j \}_{j=0}^{p-1} и теорема доказана: \operatorname{Card} (\mathbb F) = p. Предположим, что существует \mathfrak A \in \mathbb F и \mathfrak A \not\in \{ \mathfrak a_j \}_{j=0}^{p-1}. Тогда множество

\{\mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \}_{j,k=0}^{p-1}

определяет p^2 различных элементов поля \mathbb F. Действительно, если

\mathfrak a_{j_{_1}}+ \mathfrak a_{k_{_1}} \cdot \mathfrak A = \mathfrak a_{j_{_2}}+ \mathfrak a_{k_{_2}} \cdot \mathfrak A , то \quad \mathfrak a_{j_{_1}}- \mathfrak a_{j_{_2}}=(\mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}}) \mathfrak A \ .

Если \mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}} \ne \mathfrak o, то, по доказанному в предыдущем абзаце, существует обратный к элементу \mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}} и этот элемент находится в том же множестве \{ \mathfrak a_j \}_{j=1}^{p-1}. Тогда из последнего равенства следует, что

\mathfrak A=(\mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}})^{-1} (\mathfrak a_{j_{_1}}- \mathfrak a_{j_{_2}}) \quad \Rightarrow \quad \mathfrak A \in \{ \mathfrak a_j \}_{j=0}^{p-1} \ ,

что противоречит предположению. Если же \mathfrak a_{k_{_2}}- \mathfrak a_{k_{_1}} = \mathfrak o, то тогда и \mathfrak a_{j_{_1}}-\mathfrak a_{j_{_2}} = \mathfrak o.

Если в поле \mathbb F нет других элементов, то \mathbb F =\{ \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \}_{j,k=0}^{p-1} и \operatorname{Card} (\mathbb F) = p^2. В противном случае, существует элемент \mathfrak B_{}, не входящий в это подмножество, и мы рассмотрим множество

\{ \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A + \mathfrak a_{\ell} \cdot \mathfrak B \}_{j,k,\ell=0}^{p-1} \ ,

которое определяет p^3 различных элементов поля \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+ \mathfrak e= \mathfrak b. Отсюда просто получается и второе равенство: \mathfrak b+ \mathfrak e= \mathfrak a. Итак, таблица сложения (с учетом обязательной для поля коммутативности этой операции) частично заполнена:

\begin{array}{r|rrrr} \mathbb{+} & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak e & \mathfrak e & \mathfrak o & \mathfrak b & \mathfrak a \\ \mathfrak a & \mathfrak a & \mathfrak b & & \\ \mathfrak b & \mathfrak b & \mathfrak a & & \end{array}

Пытаемся заполнить оставшиеся места. Чему может быть равна сумма \mathfrak a+ \mathfrak a? Равенство \mathfrak a+ \mathfrak a = \mathfrak a невозможно, поскольку из него следовало бы, что \mathfrak a = \mathfrak o. Если \mathfrak a+ \mathfrak a = \mathfrak b, то прибавляя к обеим частям равенства \mathfrak e получим, с использованием уже заполненных частей таблицы, что \mathfrak a+ \mathfrak b = \mathfrak a, что снова приводит к неверному равенству \mathfrak b = \mathfrak o. Пусть \mathfrak a+ \mathfrak a = \mathfrak e. Для доказательства противоречивости этого равенства приходится использовать операцию умножения. По аксиоме поля 8 , имеем: для элемента \mathfrak a должен существовать обратный относительно умножения; мы пока не знаем, чему он равен, но знаем, что он существует. Обозначим его y_{}, тогда \mathfrak a \cdot y = \mathfrak e. Умножим его на равенство \mathfrak a+ \mathfrak a = \mathfrak e, с использованием аксиомы 4 приходим к \mathfrak e+ \mathfrak e = y, откуда y= \mathfrak o, что невозможно. Остался единственный вариант: \mathfrak a+ \mathfrak a = \mathfrak o. Теми же самыми рассуждениями доказываем, что и \mathfrak b+ \mathfrak b = \mathfrak o.

Осталось найти \mathfrak a+ \mathfrak b. Эта сумма не может быть равна ни \mathfrak a, ни \mathfrak b, поскольку, по предположению, \mathfrak a \ne \mathfrak b. Равенство \mathfrak a+ \mathfrak b = \mathfrak o также невозможно, поскольку, прибавляя к обеим его частям \mathfrak a, и используя результат предыдущего абзаца, приходим к тому же противоречию: \mathfrak a = \mathfrak b. Таким образом, единственный оставшийся вариант: \mathfrak a+ \mathfrak b = \mathfrak e. Окончательно таблица сложения должна иметь вид:

\begin{array}{r|rrrr} \mathbb{+} & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak e & \mathfrak e & \mathfrak o & \mathfrak b & \mathfrak a \\ \mathfrak a & \mathfrak a & \mathfrak b & \mathfrak o & \mathfrak e \\ \mathfrak b & \mathfrak b & \mathfrak a & \mathfrak e & \mathfrak o \end{array}

Теперь займемся умножением. Начальную часть таблицы заполнить легко:

\begin{array}{r|rrrr} \mathbb{\times} & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o \\ \mathfrak e & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak a & \mathfrak o & \mathfrak a & & \\ \mathfrak b & \mathfrak o & \mathfrak b & & \end{array}

Чему равно произведение \mathfrak a \cdot \mathfrak a? Вариант \mathfrak a \cdot \mathfrak a = \mathfrak o отпадает, поскольку из него (домножением на обратный относительно умножения) следует \mathfrak a = \mathfrak o. Заметим, что на том же основании,

\mathfrak b \cdot \mathfrak b \ne \mathfrak o \ .

Вариант \mathfrak a \cdot \mathfrak a = \mathfrak a влечет за собой \mathfrak a = \mathfrak e, что также невозможно. Возможно ли, чтобы \mathfrak a \cdot \mathfrak a = \mathfrak e, т.е. чтобы элемент \mathfrak a был обратен самому себе? С помощью таблицы сложения получим тогда цепочку следствий:

\mathfrak a \cdot \mathfrak a = \mathfrak e \quad \Rightarrow \quad \mathfrak a \cdot \mathfrak a + \mathfrak e = \mathfrak o \quad \Rightarrow \quad \mathfrak a \cdot \mathfrak a + \mathfrak a + \mathfrak a + \mathfrak e = \mathfrak o \quad \Rightarrow \quad (\mathfrak a + \mathfrak e)(\mathfrak a + \mathfrak e)= \mathfrak o \quad \Rightarrow \quad \mathfrak b \cdot \mathfrak b = \mathfrak o ;

последнее противоречит предыдущему неравенству. Итак, произведение \mathfrak a \cdot \mathfrak a может быть равно только \mathfrak b. Аналогично доказывается, что \mathfrak b \cdot \mathfrak b может быть равно только \mathfrak a.

Наконец,

\mathfrak a \cdot \mathfrak b = \mathfrak a \cdot (\mathfrak a+\mathfrak e) = \mathfrak a \cdot \mathfrak a + \mathfrak a = \mathfrak b + \mathfrak a = \mathfrak e \ .

Окончательно:

\begin{array}{r|rrrr} \mathbb{\times} & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o & \mathfrak o \\ \mathfrak e & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak a & \mathfrak o & \mathfrak a & \mathfrak b & \mathfrak e \\ \mathfrak b & \mathfrak o & \mathfrak b & \mathfrak e & \mathfrak a \end{array}

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

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

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

П

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

\mathfrak o= \left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \end{array} \right),\ \mathfrak e= \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right),\ \mathfrak a= \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right),\ \mathfrak b= \left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right).

В этом множестве операцию сложения определим как операцию сложения матриц по модулю 2_{}:

\left(\begin{array}{ll} a_{11}& a_{12} \\ a_{21}&a_{22} \end{array} \right)+ \left(\begin{array}{ll} b_{11}& b_{12} \\ b_{21}&b_{22} \end{array} \right)= \left(\begin{array}{ll} a_{11}+b_{11} \pmod{2} & a_{12}+b_{12} \pmod{2} \\ a_{21}+b_{21} \pmod{2} & a_{22}+b_{22} \pmod{2} \end{array} \right)

а операцию умножения — как операцию умножения матриц, но тоже по модулю 2_{}, т.е.:

\left(\begin{array}{ll} a_{11}& a_{12} \\ a_{21}&a_{22} \end{array} \right)\times \left(\begin{array}{ll} b_{11}& b_{12} \\ b_{21}&b_{22} \end{array} \right) = \left(\begin{array}{ll} a_{11}b_{11} +a_{12}b_{21} \pmod{2} & a_{11}b_{12} +a_{12}b_{22} \pmod{2} \\ a_{21}b_{11} +a_{22}b_{21} \pmod{2} & a_{21}b_{12} +a_{22}b_{22} \pmod{2} \end{array} \right) \ .

Можно проверить, что таблицы действий с элементами этого множества совпадают с таблицами, приведенными выше.

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

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

Т

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

\mathfrak a^{p^m} - \mathfrak a = \mathfrak o \ .

Доказательство аналогично доказательству малой теоремы Ферма. Обозначим для краткости q=p^m, и рассмотрим все ненулевые элементы поля

\mathfrak a_1,\dots, \mathfrak a_{q-1} \ .

Если \mathfrak a \ne \mathfrak o, то домножим его на все эти элементы:

\mathfrak a \mathfrak a_1,\dots, \mathfrak a \mathfrak a_{q-1} \ .

Получились снова элементы поля. Они все отличны от \mathfrak o (поскольку в поле не существует делителей нуля) и все различны:

\mathfrak a \mathfrak a_j = \mathfrak a \mathfrak a_k \quad \Rightarrow \quad \mathfrak a (\mathfrak a_j - \mathfrak a_k)= \mathfrak o \quad \Rightarrow \quad \mathfrak a = \mathfrak o \quad или \quad \mathfrak a_j = \mathfrak a_k \ .

Следовательно множество \{ \mathfrak a \mathfrak a_j \}_{j=1}^{q-1} совпадает со множеством \{ \mathfrak a_k \}_{k=1}^{q-1}, но тогда произведения элементов этих множеств одинаковы:

\prod_{j=1}^{q-1} (\mathfrak a \mathfrak a_j) = \prod_{j=1}^{q-1} \mathfrak a_j \quad \Rightarrow \quad a^{q-1} \prod_{j=1}^{q-1} \mathfrak a_j = \prod_{j=1}^{q-1} \mathfrak a_j \ .

Произведение ненулевых элементов поля отлично от \mathfrak o, следовательно

\mathfrak a^{q-1}= \mathfrak e \ ;

это равенство справедливо для любого ненулевого элемента поля. Умножив его на \mathfrak a, получим равенство из условия теоремы, которому будет удовлетворять и \mathfrak a = \mathfrak o.

Т

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

\mathfrak a^m + A_1 \mathfrak a^{m-1} + \dots + A_{m} = \mathfrak o \quad npu \quad \{ A_1,\dots,A_m \} \subset \{ \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_{p-1} \},\ \mathfrak a_{j}= \underbrace{\mathfrak e+\dots+\mathfrak e}_{j}, \quad u \quad m \in \mathbb N \ .

Будем называть выражение вида

\mathfrak x^m + A_1 \mathfrak x^{m-1} + \dots + A_{m} = \mathfrak o

при \{ A_1,\dots,A_m \} \subset \{ \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_{p-1} \} алгебраическим уравнением в \mathbf{GF}(p^m) степени m_{} относительно неизвестной \mathfrak x_{}.

Доказательство. При доказательстве теоремы 2 из предыдущего пункта было показано, что в любом поле \mathbb P найдутся m_{} элементов \mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m таких, что любой элемент поля можно выразить в виде их линейной комбинации с коэффициентами из множества \{ \mathfrak a_{j} \}_{j=0}^{p-1}. Выразим в виде таких линейных комбинаций элементы \mathfrak a, \mathfrak a \mathfrak A_1, \mathfrak a \mathfrak A_2,\dots, \mathfrak a \mathfrak A_m:

\begin{array}{lcl} \mathfrak a &=& A_{11} +A_{12} \mathfrak A_2+\dots+ A_{1m} \mathfrak A_m, \\ \mathfrak a \mathfrak A_2 &=& A_{21} +A_{22} \mathfrak A_2+\dots+ A_{2m} \mathfrak A_m, \\ \dots & & \dots \\ \mathfrak a \mathfrak A_m &=& A_{m1} +A_{m2} \mathfrak A_2+\dots+ A_{mm} \mathfrak A_m, \end{array} \qquad npu \quad \{ A_{jk} \}_{j,k=1}^m \subset \{ \mathfrak a_{j} \}_{j=0}^{p-1} \ .

Перепишем эти уравнения:

\begin{array}{cccccc} (A_{11}- \mathfrak a) & +A_{12} \mathfrak A_2 & +\dots & + A_{1m} \mathfrak A_m &=& \mathfrak o, \\ A_{21} & +(A_{22}- \mathfrak a) \mathfrak A_2 &+\dots & + A_{2m} \mathfrak A_m &=& \mathfrak o, \\ \dots & & & & & \dots \\ A_{m1} & + A_{m2} \mathfrak A_2 & +\dots+ & (A_{mm}- \mathfrak a) \mathfrak A_m &=& \mathfrak o. \end{array}

Эта система уравнений, рассматриваемая относительно элементов поля \mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m является линейной и однородной.


§

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


Поскольку эта однородная система имеет нетривиальное решение ( \mathfrak A_1=\mathfrak e\ne \mathfrak o), ее определитель должнен быть равен нулевому элементу поля:

\left|\begin{array}{cccc} A_{11}- \mathfrak a & A_{12} & \dots & A_{1m} \\ A_{21} & A_{22}- \mathfrak a& \dots & A_{2m} \\ \dots & & & \dots \\ A_{m1} & A_{m2}& \dots & A_{mm}- \mathfrak a \end{array} \right|= \mathfrak o \ .

Определитель в левой части является полиномом от \mathfrak a степени m_{} с коэффициентами, которые полиномиально же зависят от величин \{ A_{jk} \}_{j,k=1}^m, т.е., в конечном итоге, от величин \{ \mathfrak a_{j} \}_{j=0}^{p-1}.

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

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

Полином 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,-1,0,1,2\}:

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^{n-1}+\dots+a_n \in \mathbb Z[x] \ .

Доказать, что частное и остаток от деления произвольного полинома g_{} (x)\in \mathbb Z[x] на f_{}(x) будут полиномами с целыми коэффициентами.

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

!

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

Полиномы \{F_1(x),F_2(x)\} \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 \{G(x),H(x) \}\subset \mathbb Z[x] \ .

Иными словами, остаток от деления F_1(x)-F_2(x) на f_{}(x) представляет собой полином, все коэффициенты которого кратны p_{}:

\left( F_1(x)-F_2(x) \pmod{f(x)} \right) \pmod{p} \equiv 0 \ ;

здесь знак \equiv_{} обозначает тождественное равенство. В [1] для этого понятия используется обозначение

F_1(x)\equiv F_2(x) \quad (\operatorname{modd} \ 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{modd} \ p,f(x))

в том же смысле, что в разделе МОДУЛЯРНАЯ АРИФМЕТИКА использовалось обозначение x = A \pmod{M}, т.е. полиному 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{modd} \ 7,f(x)) \ .

Т

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

\mathbb P_{p,f} = \{ F (x)=A_0+A_1x+\dots+A_{m-1}x^{m-1} \ \mid \ \{A_0,A_1,\dots,A_{m-1}\} \subset \{0,1,\dots,p-1 \} \} \ ,

рассматриваемое относительно операции сложения по модулю p_{}:

F_1(x)+F_2(x) \pmod{p}

и операции умножения по двойному модулю p, f(x):

F_1(x) F_2(x) \quad (\operatorname{modd} \ p,f(x))

образует поле Галуа \mathbf{GF}(p^m).

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

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

U(x)F(x) \quad (\operatorname{modd} \ p,f(x)) \equiv 1 \ .

Если F_{}(x) тождественно равен константе F(x)\equiv A_0, то искомый полином U(x) тоже будет константой: U(x)\equiv U_0, где U_0A_0 \equiv 1 \pmod{p}. Последнее сравнение имеет решение для любого A_0\in \{1,\dots,p-1\}, это решение будет единственны в том же множестве, и оно называется мультипликативным обратным числу A_0 по модулю p_{}. Соответствующую теорию и сопутствующие алгоритмы нахождения см. ЗДЕСЬ; сугубо же для теоретических манипуляций нам достаточно будет его представления посредством малой теоремы Ферма:

A_0^{-1}= A^{p-2} \pmod{p} \ .

Предположим теперь, что F(x) \not\equiv const:

F(x) = A_0+A_1x+\dots+A_{\ell}x^{\ell} \quad npu \quad A_{\ell} \ne 0, \ell > 0 \ .
§

Вся оставшаяся часть доказательства представляет собой, фактически, алгоритм Евклида нахождения наибольшего общего делителя полиномов f_{}(x) и F_{}(x) — вместе с нахождением его линейного представления. Отличие от классического алгоритма Евклида будет заключаться в том, что по выполнении каждого деления целочисленных полиномов, мы будем избавляться от появляющихся в выражениях частных и остатков знаменателей дробей (сохраняя целочисленность полиномов). Такая операция оказывается возможной за счет того, что во множестве \{1,\dots, p-1\} можно организовать операцию деления, которая не выведет за пределы этого множества — если операция умножения этих чисел вводится по модулю простого числа p_{}.

Разделим полином f_{}(x) на F(x):

f(x)\equiv q_1(x)F(x)+r_1(x) ,

здесь \deg q_1 = m-\ell, \deg r_1 < \ell. Поскольку коэффициенты делимого и делителя целочислены, то коэффициенты частного q_1(x) и остатка r_1(x) будут рациональными числами; при этом знаменатели дробей могут быть только степенями числа A_{\ell}: \{ 1,A_{\ell},\dots, A_{\ell}^{m-\ell+1} \}. Заменим каждое рациональное число вида

\frac{B}{A_{\ell}^K}

на

B A_{\ell}^{p-K-1} \pmod{p} ;

на основании малой теоремы Ферма, числа A_{\ell}^K и A_{\ell}^{p-K-1} являются мультипликативными обратными относительно умножения по модулю p_{}:

A_{\ell}^{p-K-1}\cdot A_{\ell}^K \equiv 1 \pmod{p} \ .

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

f(x)\equiv Q_1(x)F(x)+R_1(x) ,

но справедливый теперь по модулю p_{}. Может ли полином R_1(x) оказаться тождественно равным 0_{} ? — Нет, поскольку при выполнении этого предположения, мы пришли бы к противоречию с тем фактом, что f_{}, по предположению, является неприводимым полиномом по модулю p_{}. Итак, R_1(x) не равен тождественно 0_{}. Пусть он тождественно равен ненулевой константе R_1(x) \equiv C_0 при C_0\in \{1,\dots,p-1\}. Домножим тождество

f(x)\equiv Q_1(x)F(x)+ C_0

на мультипликативное обратное числу C_0 по модулю p_{}, представив его, например, в виде C_0^{p-2} \pmod{p}. Получим

C_0^{p-2} f(x) - C_0^{p-2}Q_1(x)F(x) \equiv 1 \pmod{p} \ .

Из последнего тождества тогда следует, что в качестве полинома U(x), удовлетворяющего

U(x)F(x) \quad (\operatorname{modd} \ p,f(x)) \equiv 1 \ ,

можно взять [- C_0^{p-2}Q_1(x)] \pmod{p}.

Идем далее. Предположим, что полином R_1(x) не является константой: \deg R_1>0. Разделим целочисленный полином F_{}(x) на целочисленный полином R_1(x):

F(x) \equiv q_2(x) R_1(x) + r_2(x) , \quad \deg r_2<\deg R_1 .

Коэффициенты частного q_2(x) и остатка r_2(x) будут рациональными числами; при этом знаменатели дробей могут быть только степенями старшего коэффициента полинома R_1(x). Повторяем процедуру избавления от знаменателей, использованную в предыдущем абзаце. Приходим к целочисленному тождеству

F(x)\equiv Q_2(x) R_1(x) + R_2(x) \ ,

справедливому по модулю p_{}. Если полином R_2(x) тождественно равен константе: R_2(x) \equiv D_0, то эта константа не должна быть нулем. В противном случае3)

F(x)\equiv Q_2(x) R_1(x) \quad \Rightarrow \quad f(x)\equiv Q_1(x)F(x)+R_1(x) \equiv R_1(x) (Q_1(x)Q_2(x)+1) \ ,

откуда вытекает приводимость полинома f_{}(x) по модулю p_{}. Домножаем тождество

F(x)\equiv Q_2(x) R_1(x) + D_0

на мультипликативное обратное числу D_0 по модулю p_{}, представив его, например, в виде D_0^{p-2} \pmod{p}. Получим

D_0^{p-2} F(x) - D_0^{p-2}Q_2(x)R_1(x) \equiv 1 \pmod{p} \ .

Подставим в это тождество представление для R_1(x) из его определения в предыдущем абзаце:

R_1(x) \equiv f(x)- Q_1(x)F(x),

приходим к тождеству

D_0^{p-2} (Q_1(x)Q_2(x)+1)F(x)-D_0^{p-2}Q_2(x)f(x) \equiv 1 .

Из него следует, что в качестве полинома U(x), удовлетворяющего

U(x)F(x) \quad (\operatorname{modd} \ p,f(x)) \equiv 1 \ ,

можно взять D_0^{p-2} (Q_1(x)Q_2(x)+1) \pmod{p}.

Наконец, если полином R_2(x) не является константой: \deg R_2>0, то разделим целочисленный полином R_1(x) на целочисленный полином R_2(x):

R_1(x) \equiv q_3(x) R_2(x) + r_3(x) , \quad \deg r_3<\deg R_2 .

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

R_{k-2}(x)\equiv Q_k(x) R_{k-1}(x)+ R_k

и R_k \not\equiv 0 \pmod{p}. Умножив тождество на R_k^{p-2} приведем его к виду

1\equiv R_k^{p-2} R_{k-2}(x)- R_k^{p-2} Q_k(x) R_{k-1}(x) \ .

Далее возвращаемся назад в алгоритме последовательного деления. Из предпоследнего шага можно выразить R_{k-1}(x) через R_{k-2} (x) и R_{k-3} (x), подставив их выражения в последнее тождество, получим

1\equiv R_k^{p-2}[1+Q_k(x)Q_{k-1}(x)] R_{k-2}(x)- R_k^{p-2} Q_k(x) R_{k-3}(x) \ .

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

1 \equiv V(x)f(x)+U(x)F(x) \ .

Но оно эквивалентно искомому

U(x)F(x) \quad (\operatorname{modd} \ p,f(x)) \equiv 1 \ .

Практическое нахождение элемента, обратного в поле Галуа заданному, возможно разными способами. Все они, прямо или опосредовано, завязаны на полиномиальное тождество, известное под названием тождества Безу: это тождество имеет вид

v(x)f(x)+u(x)g(x)\equiv 1 \ .

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

П

Пример. В поле \mathbf{GF}(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{1561}{650}-\frac{33}{1300}x-\frac{22}{325}x^2+\frac{307}{1300}x^3-\frac{1023}{1300}x^4, \quad v(x)\equiv \dots

Далее, решаем сравнения

650\,z_1 \equiv 1,\ 1300 \,z_2 \equiv 1,\ 325 \, z_3 \equiv 1 \pmod{7}

получаем мультипликативные обратные к знаменателям z_1=6,z_2=3,z_3=5 \pmod{7}. Избавляемся от знаменателей в коэффициентах полинома u_{}(x):

U(x)=-1561 \cdot 6-33\cdot 3\,x -22\cdot 5\,x^2+307\cdot 3\,x^3-1023 \cdot 3\,x^4 \equiv_{7} \dots

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

§

Строгое — с формальной точки зрения — введение объекта \mathbb P_{p,f} предыдущей теоремы должно было производиться на основе классов вычетов по модулю p_{}:

\mathbb P_{p,f} = \{ F (x)=A_0+A_1x+\dots+A_{m-1}x^{m-1} \ \mid \ \{A_0,A_1,\dots,A_{m-1}\} \subset \{\overline 0, \overline 1,\dots, \overline{p-1} \} \} \ .

Я пренебрег строгостью в ущерб наглядности. Из этих же соображений5), часто ниже буду использовать тот же объект в варианте

\mathbb P_{p,f} = \left\{ \begin{array}{c|l} F (x)=A_0+A_1x+\dots+A_{m-1}x^{m-1} & \{A_0,A_1,\dots,A_{m-1}\} \subset \\ & \subset \left\{-\frac{p-1}{2}, -\frac{p-1}{2}+1,\dots,-1, 0, 1, 2,\dots, \frac{p-1}{2} \right\} \end{array} \right\} \ ,

для нечетных простых чисел p_{}. Иногда это более удобно по сравнению с использованной в теореме версией, — хотя бы потому, что коэффициенты полиномов F_{}(x) уменьшаются по абсолютной величине.

П

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

Решение. Здесь p=2 и m_{}=2. Полином f(x)=x^2+x+1 является неприводимым по модулю 2_{}. Согласно теореме, множество из четырех полиномов \{0,1,x,x+1\} с операцией сложения по модулю 2_{} и операцией умножения по двойному модулю 2, x^2+x+1 образует поле. Результаты операций, собранные в таблицы

\begin{array}{c|cccc} \mathbb{+} & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1 \\ x+1 & x+1 & x & 1 & 0 \end{array} \qquad \qquad \begin{array}{c|cccc} \mathbb{\times} & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1 \\ x+1 & 0 & x+1 & 1 & x \end{array}

полностью соответствуют приведенным в начале раздела, где выводились правила действий в произвольном поле \mathbf{GF}(4). Иными словами, существует изоморфизм между произвольным полем \mathbf{GF}(4) (например полем из четырех матриц, построенным в конце ПУНКТА ) и полем из полиномов, построенным в настоящем примере.

Т

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

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

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

!

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

Т

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

Доказательство. В предыдущем пункте было доказано, что если f_{}(x) неприводимый по модулю p_{} полином степени n_{}, то множество \mathbb P_{p,f} полиномов степеней < n с коэффициентами из \{0,1,\dots,p-1\} образует поле Галуа \mathbf{GF} (p^n) относительно введенных операций сложения по модулю p_{} и умножения по двойному модулю p,f(x). Но тогда любой полином F(x) \in \mathbb P_{p,f} должен удовлетворять обобщенной теореме Ферма:

\left[F(x)\right]^{p^n} - F(x) \equiv 0 \quad (\operatorname{modd} \ p,f(x)) \ .

В частности, это должно быть справедливо и для F(x) \equiv x. Тогда полином

x^{p^n}-x

должен делиться на полином f_{} (x) по модулю p_{}.

§

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

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

Т

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

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

Т

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

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

Т

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

p^m=\sum_{k} k \xi_p (k) \ ;

здесь суммирование производится по всем индексам k_{} , являющимися делителями числа m_{}.

?

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

=>

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

\xi_p (m) =\frac{1}{m} \left(p^m- \sum_{k_1} p^{m/k_{_1}}+\sum_{k_{_1},k_{_2}} p^{m/(k_{_1}k_{_2})}- \sum_{k_{_1},k_{_2},k_{_3}} p^{m/(k_{_1}k_{_2}k_{_3})} + \dots \right) \ ,

где k_1,k_2,k_3,\dots пробегают всевозможные делители числа m_{}.

П

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

Решение. Поскольку 30=2\cdot 3 \cdot 5, то имеем:

\xi_p (30) = \frac{1}{30} \left(p^{30}-p^{15}-p^{10}-p^6+p^5+p^3+p^2-p \right) \ .

Так, \xi_2 (30)= 35790267,\ \xi_3 (30) =6863037256208.

В поле Галуа первообразным корнем степени n из единицы называется элемент \mathfrak a, который удовлетворяет условиям

\mathfrak a^n=\mathfrak e \ , \mathfrak a^k \ne \mathfrak e \quad npu \quad k\in \{1,2,\dots,n-1\} \ .

Будем также говорить, что \mathfrak a принадлежит показателю n или, что \mathfrak a имеет порядок n.

§

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

Т

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

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

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

=>

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

=>

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

П

Пример 1. Пусть p=3, m=2. Выбрав в качестве неприводимого по модулю 3_{} полинома7) f(x)=x^2-x-1, получим, что элементами поля \mathbf{GF} (3^2) должны быть полиномы степени не выше 1_{} с коэффициентами из множества \{-1,0,1\}. Возьмем в качестве примитивного элемента поля полином тождественно равный8) x_{}. Получим, последовательным возведением его в степень:

x^0\equiv 1,\ x^1\equiv x,\ x^2 \equiv x+1 \quad (\operatorname{modd} \ 3,x^2-x-1 ) , \ x^3\equiv x\cdot x^2 \equiv x^2+x\equiv 2\,x+1 \equiv - x+1 ,

т.е. каждый раз умножаем результат предыдущего шага на x_{} и в правой части производим формальную замену x^2 \to x+1;

\begin{array}{l} x^4\equiv -x^2+x \equiv -x-1+x\equiv -1,\\ x^5 \equiv -x,\\ x^6 \equiv -x^2 \equiv -x-1,\\ x^7 \equiv -x^2-x\equiv -x-1-x \equiv x-1, \\ x^8 \equiv x^2-x \equiv 1 \ . \end{array}

Цикл завершен.

Т

Теорема 6. Полином x^{p^m}- x содержит неприводимые по модулю p_{} сомножители степени m_{}.

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

П

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

Решение. Воспользуемся результатом из пункта УРАВНЕНИЕ ДЕЛЕНИЯ КРУГА.

x^{16}-x \equiv x \left(x^{15}-1 \right) \equiv x\, X_1(x)X_3(x)X_5(x)X_{15}(x) \equiv
\equiv x(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^8-x^7+x^5-x^4+x^3-x+1) \ .

Здесь полиномы X_j(x) — неприводимы в \mathbb Z_{}. Чтобы найти разложение на неприводимые по модулю 2_{} полиномы, воспользуемся сначала результатом теоремы 3 для определения количества этих неприводимых полиномов. Имеем:

\begin{array}{rcrrr} 16 & = & 4 \xi (4) & + 2\xi (2) & + \xi (1), \\ 4 & = & & 2\xi (2) & + \xi (1), \\ 2 & = & & & \xi (1), \end{array}

откуда: \xi (1)=2, \xi (2)=1, \xi (4)=3. Таким образом, получаем что по модулю 2_{} имеется (в-точности) 2_{} неприводимых линейных полинома, оба уже наблюдаются в разложении:

x \quad и \quad x-1 \equiv x+1 \pmod{2} \ ;

Неприводимый полином 2_{}-й степени единствен — и он также уже содержится в разложении:

x^2+x+1 \ .

Что касается неприводимых полиномов 4_{}-й степени, то их должно быть 3_{}. Один из них уже содержится в разложении:

x^4+x^3+x^2+x+1 \ ;

два остальных содержатся в разложении x^8-x^7+x^5-x^4+x^3-x+1 на множители по модулю 2_{}:

x^8-x^7+x^5-x^4+x^3-x+1 \equiv (x^4+x^3+1)(x^4+x+1) \pmod{2} \ .

П

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

Решение. Для получения этих полиномов — в соответствии с теоремой 3 — надо разложить на множители полином x^{2^3}-x. Имеем

x^{8}-x\equiv x(x-1)(x^6+x^5+x^4+x^3+x^2+x+1) \equiv x(x-1)(x^3+x^2+1)(x^3+x+1) \pmod 2 \ .

Оба полученных полинома 3_{}-й степени неприводимы по модулю 2_{}, поскольку по теореме 3 получаем

\begin{array}{rcrr} 4 & = & 3\xi (3) & + \xi (1), \\ 2 & = & & \xi (1), \end{array}

откуда \xi (3)=2.

П

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

Решение. Здесь p=3,m=2 и из теоремы имеем

\begin{array}{rcrr} 9 & = & 2\xi (2) & + \xi (1), \\ 3 & = & & \xi (1), \end{array}

т.е. \xi (1)=3, \xi (2)=3. Разложим полином x^{9}-x на неприводимые множители над \mathbb Z_{}:

x^{9}-x \equiv x(x-1)(x+1)(x^2+1)(x^4+1) \ .

Здесь полином x^2+1 должен быть неприводим по модулю 3_{}. Полином x^4+1 должен раскладываться по модулю 3_{} на два множителя 2_{}-й степени. Будем искать один из этих множителей методом неопределенных коэффициентов. Если взять его равным x^2+ax+b, то результатом деления на него полинома x^4+1 будет

x^4+1 \equiv (x^2+ax+b)(x^2-ax+a^2-b)+a(2b-a^2)x+(b^2-a^2b+1) \ .

Коэффициенты остатка приравняем нулю по модулю 3_{}:

a(2b-a^2)\equiv_{_{3}} 0 ,\ b^2-a^2b+1 \equiv_{_{3}} 0 \ .

Если из первого сравнения взять a \equiv_{_{3}} 0, то из второго сравнения получим b^2+1 \equiv_{_{3}} 0. Это сравнение решений не имеет9). Следовательно, из первого сравнения надо выбрать альтернативный вариант:

a^2 \equiv_{_{3}} 2 b \quad \iff \quad a^2 \equiv_{_{3}} -b ;

подставляем его во второе сравнение:

2b^2+1 \equiv_{_{3}} 0 \quad \iff \quad - b^2+1 \equiv_{_{3}} 0 \quad \iff \quad b \equiv_{_{3}} \pm 1 \ .

Если b \equiv_{_{3}} 1, то a^2 \equiv_{_{3}} - 1 или a^2 \equiv_{_{3}} 1. Первое сравнение невозможно. Неприводимыми по модулю 3_{} полиномами 2_{}-й степени являются x^2+x-1 и x^2-x-1.

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

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

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

?

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

П

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

Решение. Поле содержит 16_{} элементов: полиномов вида A_0x^3+A_1x^2+A_2x+A_3 при \{A_0,A_1,A_2,A_3\} \in \{1,2\}. Теперь надо определить операцию умножения. Разложение полинома x^{16}-x на неприводимые по модулю 2_{} множители приведено в предыдущем пункте:

x^{16}-x \equiv_{_{2}} x(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^4+x^3+1)(x^4+x+1) \ .

При любом выборе неприводимого полинома f_{}(x) степени 4_{} из трех, участвующих в этом разложении, операция умножения по двойному модулю 2,f(x) будет удовлетворять аксиомам поля. Проверим это для выбора f_{}(x)=x^4+x+1. Следующая таблица выражает все полиномы из поля через посредство выражений для степеней \{x^{k} \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14}:

\begin{array}{l|rrrr|c|c} x^0 & & & & 1 & 0001 & \\ x^1 & & & x & & 0010 & \Pi \\ x^2 & & x^2 & & & 0100 & \Pi \\ x^3 & x^3 & & & & 1000 & \\ \hline x^4 & & & x & +1 & 0011 & \Pi \\ x^5 & & x^2 & +x & & 0110 & \\ x^6 & x^3 & +x^2 & & & 1100 & \\ x^7 & x^3 & & + x & +1 & 1011 & \Pi \\ \hline x^8 & & x^2 & & +1 & 0101 & \Pi \\ x^9 & x^3 & & +x & & 1010 \\ x^{10} & & x^2 &+x & +1 & 0111 \\ x^{11} & x^3 & +x^2 & +x & & 1110 & \Pi \\ \hline x^{12} & x^3 & +x^2 & + x& +1 & 1111 \\ x^{13} & x^3 & +x^2 & & +1 & 1101 & \Pi \\ x^{14} & x^3 & & & +1 & 1001 & \Pi \end{array}

(и если бы мы продолжили эту таблицу, то следующим шагом вышли бы на цикл: x^{15} \quad (\operatorname{modd} \ 2,f(x)) \equiv 1). В третьем столбце стоят двоичные наборы коэффициентов полиномов, рассматриваемых в разложении по убывающим степеням x_{}. В четвертом столбце отмечены примитивные элементы поля, т.е. элементы, степени которых порождают все ненулевые элементы поля (одним из них являлся полином, тождественно равный x_{}, по которому, собственно, и составлена таблица; с тем же успехом мы могли бы рассматривать и \{\left(x^2\right)^k \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14} или \{\left(x^{11}\right)^k \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14}, и т.п.). Количество примитивных элементов равно \phi(2^4-1)=\phi(15)=8. Все они обязаны удовлетворять алгебраическим уравнениям, степеней равных делителям числа 16_{}. Все эти уравнения можно получить из разложения полинома x^{16} - x на неприводимые по модулю 2_{} множители. Проверим это. Чтобы избежать путаницы, будем рассматривать неприводимые полиномы относительно переменной \mathfrak x. Проверяем, что полиномы x, x^2,x^4,x^8 удовлетворяют уравнению \mathfrak x^4+\mathfrak x+\mathfrak e= \mathfrak o; везде ниже сравнения вычисляются по двойному модулю 2,x^4+x+1:

x^4+x+1 \equiv 0,\ (x^2)^4+(x^2)+1 \equiv x^8+x^2+1 \equiv x^2+1+x^2+1 \equiv 0,
\begin{matrix} (x^4)^4+(x^4)+1 & \equiv &(x+1)^4+(x+1)+1 \equiv x+(x+1)+1 \equiv 0 , \\ (x^8)^4+(x^8)+1 & \equiv & (x^{2}+1)^4+(x^2+1)+1 \equiv x^2+(x^2+1)+1 \equiv 0 \ . \end{matrix}

Оставшиеся 4_{} примитивных элемента поля, именно, x^7,x^{11},x^{13},x^{14} должны удовлетворять другому уравнению 4_{}-й степени, которое соответствует одному из оставшихся неприводимых полиномов этой степени. В самом деле, они удовлетворяют уравнению \mathfrak x^4+\mathfrak x^3+\mathfrak e= \mathfrak o:

(x^7)^4 + (x^7)^3+1 \equiv x^{28}+x^{21}+1 \equiv x^{13}+x^{6}+1\equiv x^3+x^2+1+(x^3+x^2)+1 \equiv 0 \ .

Последние вычисления проводились с учетом x^{15} \equiv 1 и с использованием построенной выше таблицы для степеней x^{k}.

Примитивные элементы поля, т.е. элементы порядка 15_{}, исчерпаны. Все остальные элементы поля имеют порядки, равные 1_{}, 3_{} или 5_{}, т.е. — в соответствии с теоремой предыдущего пункта — делителям числа 15_{}. Рассмотрим последовательность \{\left(x^3\right)^k \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14}:

(x^3)^0 \equiv 1,\ (x^3)^1 \equiv x^3,\ (x^3)^2 \equiv x^6 \equiv x^3 +x^2,\ (x^3)^3 \equiv x^9 \equiv x^3 +x,\ (x^3)^4 \equiv x^{12} \equiv x^3 +x^2+x+1,\ (x^3)^5 \equiv x^{15} \equiv 1 \ .

Итак, элемент поля x^{3} принадлежит показателю 5_{}, этому же показателю принадлежат и его степени, т.е. полиномы x^3 +x^2,\ x^3 +x,\ x^3 +x^2+x+1. Все эти полиномы удовлетворяют уравнению \mathfrak x^4+\mathfrak x^3+\mathfrak x^2+\mathfrak x+\mathfrak e= \mathfrak o, соответствующему третьему неприводимому полиному 4_{}-й степени из разложения x^{16}-x. На всякий случай, осуществим выборочную проверку:

(x^9)^4+(x^9)^3+(x^9)^2+x^9+1 \equiv x^{6}+x^{12}+x^3+x^9+1 \equiv (x^3+x^2)+(x^3+x^2+x+1)+x^3+(x^3+x)+1 \equiv 0 \ .

Теперь рассмотрим оставшиеся элементы поля: x^5 и x^{10}. Они должны принадлежать показателю 3_{}, что и немедленно проверяется. Кроме того, они должны удовлетворять неприводимому уравнению из разложения x^{16}-x. Выбор однозначен — единственным кандидатом является уравнение 2_{}-й степени \mathfrak x^2+ \mathfrak x + \mathfrak e = \mathfrak o:

(x^5)^2+x^5+1 \equiv x^2+x+1 + (x^2+x)+1 \equiv 0 \ .

Наконец, нейтральные элементы поля 0_{} и 1_{} — с ними все просто.

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

?

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

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

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

\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} k & 1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 12 & 21 & 25 & 30 \\ \hline \xi(k) & 2 & 1 & 2 & 3 & 6 & 9 & 18 & 30 & 56 & 99 & 335 & 99858 & 1342176 & 35790268 \\ \hline \xi(k)/2^k & 1 & 0.25 & 0.25 & 0.19 & 0.19 & 0.14 & 0.14 & 0.12 & 0.11 & 0.10 & 0.08 & 0.05 & 0.04 & 0.03 \end{array}
?

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

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

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

Теперь обобщим результаты разобранных в предыдущем пункте примеров. Будем рассматривать полиномы F_{}(x) над \mathbf{GF}(p). Нас будут интересовать решения уравнения

F(\mathfrak x) \equiv \mathfrak o \ .

среди элементов конечного поля \mathbf{GF}(p^m). Любой такой элемент \mathfrak a будем называть корнем полинома F_{} в поле \mathbf{GF}(p^m).

Т

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

\mathfrak a, \mathfrak a^p, \mathfrak a^{p^2},\dots, \mathfrak a^{p^{n-1}} \ .

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

\left[F(x)\right]^p \equiv F(x^p) \pmod{p} \ .

Тогда если F(\mathfrak a)= \mathfrak o, то и F(\mathfrak a^p)= \mathfrak o, но тогда и F((\mathfrak a^p)^p)= \mathfrak o, и т.д. С другой стороны, все элементы множества \{ \mathfrak a^{p^j} \}_{j=0}^{n-1} различны. Действительно, если бы выполнялось равенство

\mathfrak a^{p^j}=\mathfrak a^{p^k} \qquad npu \qquad 0\le j< k \le n-1 \ ,

то возведением его в степень p^{n-k}, получим равенство

\mathfrak a^{p^{n+j-k}}=\mathfrak a^{p^n} = \mathfrak a \ .

Последнее равенство следует из доказательства теоремы из ПУНКТА. Однако равенство

\mathfrak a^{p^{n+j-k}}= \mathfrak a

невозможно, поскольку n+j-k< n, а, ввиду теоремы 3 из ПУНКТА, полином x^{p^{n+j-k}}-x делится лишь на такие неприводимые по модулю p_{} полиномы, степени которых являются делителями числа n+j-k и, следовательно, не может делиться на F_{}(x).

Т

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

Показатель корней неприводимого полинома называется показателем, которому этот полином принадлежит. Если неприводимый полином F_{}(x) принадлежит показателю \ell_{}, то он является делителем полинома x^{\ell}-1, но не является делителем ни одного из полиномов x^k-1 при k\in \{1,\dots,\ell-1 \}. Неприводимый полином степени m_{} над \mathbf{GF}(p) называется примитивным, если его корнем является примитивный элемент поля \mathbf{GF}(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 \{1,\dots,p^m-2 \}. Если каноническое разложение числа p^m-1 имеет вид:

p^m-1=p_1^{{\mathfrak m}_{_1}}p_2^{{\mathfrak m}_{_2}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{_{\mathfrak r}}} \ ,

то для того чтобы неприводимый полином F_{}(x) степени m_{} был примитивным, необходимо и достаточно, чтобы он не являлся делителем ни одного из полиномов x^{(p^m-1)/p_j}-1 при \forall j \in \{1,\dots, \mathfrak r \}.

П

Пример. Из трех неприводимых полиномов 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. Текст ЗДЕСЬ.

1) Galois field
2) Как они не освещены и в [1], откуда я этот результат взял.
3) Все тождества далее — если не обговорено особо — рассматриваются по модулю p_{}.
4) Выражение для v_{}(x) нас совершенно не интересует.
5) и без дополнительных предупреждений
6) Иногда будем использовать это обозначение без индекса, если по контексту понятно о каком модуле p_{} идет речь.
7) См. пример 4 ниже.
8) Заметим, что выбор примитивного элемента поля не всегда тривиален, и не всегда в качестве этого элемента можно взять x_{}; но, по крайней мере, проверить конкретный элемент на примитивность принципиально возможно — см. теорему 2 ЗДЕСЬ.
9) Проверяется подстановкой b\in \{-1,0,1\}.

2017/10/19 18:55 редактировал au