Инструменты сайта


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


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

}}


!

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


Поля Галуа

§

В настоящем разделе буква $ 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 \mbox{ при } \quad p \mbox{ - простом и } \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 ,\ \mbox{ то } \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 \mbox{ или } \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 \mbox{ и } \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\} $.
gruppe/galois.txt · Последние изменения: 2020/03/11 14:00 (внешнее изменение)