!!§!! Вспомогательная страница к разделу
☞
((:gruppe:galois#полиномы_над_gf_2 ПОЛЯ ГАЛУА)).
----
==Поле GF(16)==
**Задача.** Исследовать поле $ \mathbf{GF}(16) $ для разных выборов неприводимых полиномов $ 4_{}- $й степени.
Поле содержит $ 16_{} $ элементов: полиномов вида $ A_0x^3+A_1x^2+A_2x+A_3 $ при $ \{A_0,A_1\} \in \{1,2\} $. Теперь надо определить операцию умножения.
Разложение полинома $ x^{16}-x $ на неприводимые по модулю $ 2_{} $ множители приведено
☞
((:gruppe:galois#полиномы_неприводимые_по_модулю ЗДЕСЬ)):
$$ x^{16}-x \equiv_{_{2}} x(x-1)(x^2+x+1)\underbrace{(x^4+x+1)}_{\equiv f_{_1}(x)}\underbrace{(x^4+x^3+1)}_{\equiv f_{_2}(x)} \underbrace{(x^4+x^3+x^2+x+1)}_{\equiv f_{_3}(x)}\ . $$
При любом выборе неприводимого полинома $ f_j(x) $ степени $ 4_{} $ из трех, участвующих в этом разложении, операция умножения по двойному модулю $ 2,f_j(x) $ будет удовлетворять аксиомам поля. Следующие таблицы выражают все полиномы из поля через посредство выражений для степеней $ \{\mathfrak A^{k} \quad (\operatorname{modd} \ 2,f_j(x)) \}_{k=0}^{14} $ для разных выборов $ f_j(x) $ и ((:gruppe:galois:vspom2 примитивного элемента)) $ \mathfrak A $:
$$
\begin{array}{c}
(\operatorname{modd} \ 2,x^4+x+1) \\
\hline \\
\begin{array}{l|rrrr|c|c|c||}
x^0 & & & & 1 & 0001 & & \\
x^1 & & & x & & 0010 & \Pi & f_1=0 \\
x^2 & & x^2 & & & 0100 & \Pi & f_1=0 \\
x^3 & x^3 & & & & 1000 & & f_3=0 \\
\hline
x^4 & & & x & +1 & 0011 & \Pi & f_1=0 \\
x^5 & & x^2 & +x & & 0110 & & \\
x^6 & x^3 & +x^2 & & & 1100 & & f_3=0\\
x^7 & x^3 & & + x & +1 & 1011 & \Pi & f_2=0 \\
\hline
x^8 & & x^2 & & +1 & 0101 & \Pi & f_1=0 \\
x^9 & x^3 & & +x & & 1010 & & f_3=0 \\
x^{10} & & x^2 &+x & +1 & 0111 & & \\
x^{11} & x^3 & +x^2 & +x & & 1110 & \Pi & f_2=0 \\
\hline
x^{12} & x^3 & +x^2 & + x& +1 & 1111 & & f_3=0 \\
x^{13} & x^3 & +x^2 & & +1 & 1101 & \Pi & f_2=0 \\
x^{14} & x^3 & & & +1 & 1001 & \Pi & f_2=0
\end{array}
\end{array} \qquad \qquad
\begin{array}{c}
(\operatorname{modd} \ 2,x^4+x^3+1) \\
\hline \\
\begin{array}{l|rrrr|c|c|c||}
x^0 & & & & 1 & 0001 & & \\
x^1 & & & x & & 0010 & \Pi & f_2=0 \\
x^2 & & x^2 & & & 0100 & \Pi & f_2=0 \\
x^3 & x^3 & & & & 1000 & & f_3=0\\
\hline
x^4 & x^3 & & & +1 & 1001 & \Pi & f_2=0 \\
x^5 & x^3 & & +x &+1 & 1011 & & \\
x^6 & x^3 & +x^2 &+x &+1 & 1111 & & f_3=0\\
x^7 & & x^2 & + x & +1 & 0111 & \Pi & f_1=0 \\
\hline
x^8 & x^3& +x^2 &+x & & 1110 & \Pi & f_2=0 \\
x^9 & & x^2& &+1 & 0101 & & f_3=0 \\
x^{10} &x^3 & &+x & & 1010 & &\\
x^{11} & x^3 & +x^2 & &+1 & 1101 & \Pi & f_1=0 \\
\hline
x^{12} & & & x& +1 & 0011 & & f_3=0 \\
x^{13} & & x^2 &+x & & 0110 & \Pi & f_1=0
\\
x^{14} & x^3 &+x^2 & & & 1100 & \Pi & f_1=0
\end{array}
\end{array}
$$
В последних столбцах указаны уравнения вида $ f_j(\mathfrak x)=0 $, которым удовлетворяют соответствующие элементы полей.
В обоих случаях в качестве примитивного элемента $ \mathfrak A $ можно было выбрать полином, тождественно равный $ x_{} $. Но вот для случая выбора в качестве модуля полинома $ f_{3}(x) $, этот кандидат не работает:
$$
\begin{array}{c}
(\operatorname{modd} \ 2,x^4+x^3+x^2+x+1) \\
\hline \\
\begin{array}{l|rrrr}
x^0 & & & & 1 \\
x^1 & & & x & \\
x^2 & & x^2 && \\
x^3 & x^3 &&& \\
x^4 & x^3 &+x^2 & +x & +1 \\
x^5 & & & & 1 \\
\vdots & & & &
\end{array}
\end{array}
$$
и ни какая степень $ x_{} $ не будет примитивным элементом поля $ \mathbf{GF}(16) $. Для этого случая в качестве примитивного элемента можно выбрать $ \mathfrak A = x+1 $:
$$
\begin{array}{c}
(\operatorname{modd} \ 2,x^4+x^3+x^2+x+1) \\
\hline \\
\begin{array}{l|rrrr|c|rrrr|c|c|c||}
(x+1)^0 & & & & 1 & 0001 & & & & 1 & 0001 & \\
(x+1)^1 & & & x &+1 & 0011 & & & (x+1) & & 0010 & \Pi & f_2=0 \\
(x+1)^2 & & x^2 & &+1 & 0101 & & (x+1)^2 & & & 0100 & \Pi & f_2=0 \\
(x+1)^3 & x^3 & +x^2&+x &+1 & 1111 & (x+1)^3 & & & & 1000 & & f_3=0 \\
\hline
(x+1)^4 & x^3 &+x^2 & +x & & 1110 & (x+1)^3 & & & +1 & 1001 & \Pi & f_2=0 \\
(x+1)^5 & x^3&+ x^2 &&+1 & 1101 & (x+1)^3 & &+(x+1) & +1 & 1011 & & \\
(x+1)^6 & x^3 & & & & 1000 & (x+1)^3 &+(x+1)^2 &+(x+1) & +1 & 1111 & & f_3=0\\
(x+1)^7 & & x^2& + x & +1 & 0111 & &(x+1)^2 &+(x+1) & +1 & 0111 & \Pi & f_1=0 \\
\hline
(x+1)^8 & & x^3 & & +1 & 1001 & (x+1)^3 &+(x+1)^2 &+(x+1) & & 1110 & \Pi & f_2=0 \\
(x+1)^9 & & x^2& & & 0100 & &(x+1)^2 & & +1 & 0101 & & f_3=0 \\
(x+1)^{10} &x^3 & +x^2 & & & 1100 & (x+1)^3 & & +(x+1) & & 1010 & & \\
(x+1)^{11} & x^3 & & +x &+1 & 1011 & (x+1)^3 & +(x+1)^2 & & +1 & 1101 & \Pi & f_1=0 \\
\hline
(x+1)^{12} & & & x& & 0010 & & & (x+1) & +1 & 0011 & & f_3=0 \\
(x+1)^{13} & & x^2 &+x & & 0110 & & (x+1)^2 & +(x+1) & & 0110 & \Pi & f_1=0 \\
(x+1)^{14} & x^3 & &+x & & 1010 & (x+1)^3 & + (x+1)^2 & & & 1100 & \Pi & f_1=0
\end{array}
\end{array}
$$
Итак, три неприводимых полинома $ 4_{} $-й степени определяют три разных поля $ \mathbf{GF}(16) $. Теорема, приведенная в конце
☞
((:gruppe:galois#пример_конечного_поля ПУНКТА)), утверждает, что эти поля изоморфны, т.е. что между их элементами можно установить взаимно-однозначное соответствие, которое сохраняет результаты обеих операций --- сложения и умножения. Проверим это. Изоморфизм первых двух полей устанавливается соответствием:
$$ x^k \quad (\operatorname{modd} \ 2,x^4+x+1) \leftrightarrow x^{15-k} \quad (\operatorname{modd} \ 2,x^4+x^3+1) \quad npu \quad k\in \{0,1,2,\dots,14\} \ . $$
Проверка сохранения операции умножения тривиальна, поскольку оба поля являются циклическими группами относительно умножения (по двойным модулям $ 2,f_j(x) $) порядка $ 15 $:
$$ x^k \cdot x^{\ell}=x^{k+\ell \pmod{15}} \leftrightarrow x^{15-k} \cdot x^{15-\ell}=x^{30-(k+\ell) \pmod{15}}=x^{15-(k+\ell) \pmod{15}} \ . $$
С проверкой сохранения результатов сложения оказывается не все просто. Обозначим остаток от деления
$ x^{k} $ на $ f_{1}(x) $ через $ r_{1}(x) $, а остаток от деления $ x^{15-k} $ на $ f_{2}(x) $ через $ r_2(x) $
Пусть
$$ x^k \equiv f_1(x)q_1(x) +r_1(x) \quad u \quad x^{15-k} \equiv f_2(x)q_2(x) +r_2(x) \ . $$
Установим зависимость между остатками $ r_1(x) $ и $ r_2(x) $. Имеем:
$$ x^k \equiv f_1(x)q_1(x) +r_1(x) \quad \Rightarrow \quad 1/x^k \equiv f_1(1/x)q_1(1/x) +r_1(1/x)
\Rightarrow \quad x^{15}/x^k \equiv x^{15}f_1(1/x)q_1(1/x) +x^{15}r_1(1/x) \Rightarrow $$
$$ \Rightarrow x^{15-k} \equiv x^{11} q_1(1/x) \left(x^4f_1(1/x) \right) +x^{12} \left(x^4r_1(1/x) \right) \ . $$
Легко проверить, что $ x^4f_1(1/x) \equiv f_2(x) $. Поскольку $ \deg q_1 = k-4 $, то выражение $ x^{k-4} q_1(1/x) $ будет полиномом по $ x_{} $, который мы обозначим[[Операция $ ^{\ast} $ описывается в
☞
((:polynomial#преобразования_корней ПУНКТЕ)).]] $ q_1^{\ast}(x) $. Аналогично,
$ x^4r_1(1/x) \equiv r_1^{\ast}(x) $ и, следовательно,
$$ x^{15-k} \equiv x^{n-k} q_1^{\ast}(x) f_2(x) +x^{12} r_1^{\ast}(x) \ . $$
Далее, согласно второй таблице, $ x^{12} \equiv x+1 \quad (\operatorname{modd} \ 2,f_2(x)) $ и в результате мы получаем соответствие между остатками
$$ r_1(x) \leftrightarrow r_2(x)= (x+1)r_1^{\ast}(x) \quad (\operatorname{modd} \ 2,f_2(x)) . $$
Если $ r_1(x) \equiv A_0+A_1x+A_2x^2+A_3x^3 $, то $ r_2(x)\equiv (A_0+A_3)+(A_2+A_3)x+(A_1+A_2)x^2+A_1x^3 $ и предложенный изоморфизм действительно сохраняет свойство линейности при сложении остатков.
Изоморфизм второго и третьего полей устанавливается соответствием:
$$ x^k \quad (\operatorname{modd} \ 2,x^4+x^3+1) \leftrightarrow (x+1)^k \quad (\operatorname{modd} \ 2,x^4+x^3+x^2+x+1) \ . $$
Здесь проверка сохранения результатов сложения оказывается более простой, чем в предыдущем случае. Если[[Обозначения аналогичны предыдущему случаю.]]
$$ x^k \equiv f_2(x)\tilde q_2(x) + \tilde r_2(x) \quad u \quad (x+1)^k \equiv f_3(x)q_3(x) +r_3(x) $$
то
$$ (x+1)^k \equiv f_2(x+1) \tilde q_2(x+1) + \tilde r_2(x+1) \ , $$
но легко устанавливается, что $ f_2(x+1) \equiv f_3(x) $. Таким образом, $ r_3(x)\equiv \tilde r_2(x+1) $ и, следовательно, изоморфизм между полями эквивалентен соответствию
$$ A_0+A_1x+A_2x^2+A_3x^3 \leftrightarrow A_0+A_1(x+1)+A_2(x+1)^2+A_3(x+1)^3 \ , $$
которое, очевидно, является линейным.
----
Теперь проанализируем некоторые наблюдения из приведенного примера.
1.
Все корни каждого из полиномов $ f_j(\mathfrak x) $ принадлежат одному показателю. Так, корни полиномов $ f_{1}(\mathfrak x) $ и $ f_2(\mathfrak x) $ являлись первообразными корнями степени $ 15 $ из единицы; корни полинома $ f_3(\mathfrak x) $ --- первообразными корнями степени $ 5_{} $ из единицы; а корни неприводимого полинома $ {\mathfrak x}^2+{\mathfrak x}+\mathfrak e $ (они не указаны в таблицах, но выделяются из них по остаточному принципу...) --- первообразными корнями степени $ 3_{} $ из единицы.
2.
Если $ F(x)=A_0+A_1x+A_2x^2+\dots+A_{n-1}x^{n-1}+A_nx^n $ --- неприводимый по модулю $ 2_{} $ полином степени $ n_{} $, то полином
$$ F^{\ast}(x) = x^n F(1/x) \equiv
A_0x^n+A_1x^{n-1}+A_2x^{n-2}+\dots+A_{n-1}x+A_n $$
также будет неприводимым полиномом.
В теории кодирования полином $ F^{\ast}(x) $, определяемый приведенным выше функциональным равенством, называется **полиномом, двойственным к** $ F_{}(x) $.
3.
Корнями одного из двух полиномов $ f_{1}(\mathfrak x) $ или $ f_{2}(\mathfrak x) $ являлись степени $ \mathfrak A, \mathfrak A^2,\mathfrak A^4, \mathfrak A^8 $ примитивного элемента поля $ \mathfrak A $. Вообще, $ 2^{k} $-я степень примитивного элемента поля $ \mathbf{GF}(2^m) $ будет примитивным элементом этого поля при любом $ k_{}\in \mathbb N $. Последнее утверждение следует из теоремы 3, приведенной
☞
((:gruppe:galois:vspom2 ЗДЕСЬ)). Из этой же теоремы будет следовать и еще один факт, не такой очевидный при визуальном просмотре таблиц приведенного примера. При $ \operatorname{HOD}(\ell,2^m-1)=1 $ произвольная степень $ (\mathfrak A^{\ell})^{2^k}, k\in \mathbb N $ примитивного элемента поля $ \mathbf{GF}(2^m) $ также будет примитивным элементом этого поля. Для поля $ \mathbf{GF}(16) $ при выборе в качестве модуля любого из полиномов $ f_{1}(x) $ или $ f_2(x) $, элемент поля $ x^7 $ будет примитивным элементом. Но тогда и $ x^{14}, x^{28},x^{56} $ --- также примитивные. Поскольку $ x^{15} \equiv 1 \quad (\operatorname{modd} \ 2,f_j(x)) $, получаем, что эти элементы совпадают с $ x^{14}, x^{13} $ и $ x^{11} $ соответственно. Именно эти элементы отмечены как примитивные в четвертых столбцах первой и второй таблиц. Чтобы покрыть случай последней таблицы, можно сделать такое обобщение. Пусть $ \mathfrak A $ является примитивным элементом какого-то из трех полей предыдущего примера. Тогда все $ 8_{} $ примитивных элементов поля разбиваются на два подмножества:
$$ \{ \mathfrak A, \mathfrak A^2,\mathfrak A^4, \mathfrak A^8 \} \quad u \quad \{ \mathfrak A^7, \mathfrak A^{14},\mathfrak A^{28}=\mathfrak A^{13}, \mathfrak A^{56}=\mathfrak A^{11} \} \ . $$
Каждое из этих подмножеств является множеством корней какого-то из полиномов $ f_1(\mathfrak x) $ или $ f_2(\mathfrak x) $. Второе подмножество кажется не таким "изящным", как первое, но если переписать его в эквивалентом виде, воспользовавшись равенством $ \mathfrak A^{-1} = \mathfrak A^{14} $, то получим
$$ \{ \mathfrak A^{-1}= \mathfrak A^{14}, \mathfrak A^{-2}=\mathfrak A^{13}, \mathfrak A^{-4}=\mathfrak A^{11},\ \mathfrak A^{-8}= \mathfrak A^7 \} \ , $$
т.е. снова $ 2^{k} $-е степени примитивного элемента $ \mathfrak A^{-1} $. Получившаяся "симметрия" множеств корней полиномов $ f_{1}(\mathfrak x) $ и $ f_{2}(\mathfrak x) $ совершенно ожидаема, поскольку корни двойственных полиномов с комплексными коэффициентами этой симметрией обладают (см. свойство
3
☞
((:polynomial#преобразования_корней ЗДЕСЬ)) ).
Подчеркнем то обстоятельство, что только что приведенное заключение будет справедливо при выборе в качестве $ \mathfrak A $ __любого__ примитивного элемента поля. Положите в предыдущем абзаце $ \mathfrak A=x^{3}+x^{2}+x $ --- и убедитесь, что справедливость выводов сохранится! Именно по этой причине таблицы элементов поля представляют не по степеням переменной $ x_{} $, а по степеням примитивного элемента $ \mathfrak A $ --- по аналогии с тем, как это сделано в $ 4_{} $-м столбце последней таблицы. Так, в рассмотренном выше примере поля $ \mathbf{GF}(16) $ при выборе в качестве модуля полинома $ f_1(x)=x^4+x+1 $ для элемента поля $ \mathfrak A^7 $ будем иметь равенство
$$ \mathfrak A^7 = \mathfrak A^3 + \mathfrak A + \mathfrak e \quad \mbox{ с двоичным представлением } \quad (1011) $$
И это представление инвариантно относительно выбора примитивного элемента $ \mathfrak A $ --- про него достаточно знать,
что он существует, имеет порядок $ 15_{} $ и удовлетворяет равенству $ \mathfrak A^4 + \mathfrak A + \mathfrak e = \mathfrak o $. Поскольку довольно часто это поле используется в примерах, приведенную выше таблицу переписал в терминах $ \mathfrak A $
☞
((:gruppe:galois:vspom4#возведение_в_степень ЗДЕСЬ)).
Совершенно аналогично проверяется, что в любом рассмотренном варианте поля $ \mathbf{GF}(16) $ множеством корней полинома $ f_3(\mathfrak x) $ является
$$ \{ \mathfrak A^3, \mathfrak A^6,\mathfrak A^{12}, \mathfrak A^{24}=\mathfrak A^9 \} \ , $$
а множеством корней полинома $ {\mathfrak x}^2+{\mathfrak x}+\mathfrak e $ является
$$ \{ \mathfrak A^5, \mathfrak A^{10} \} \ . $$
Будет ли справедливо общее утверждение, что корнями каждого из неприводимых полиномов является набор степеней некоторого элемента поля, или это только особенность рассмотренного примера
?
--- Да, будет. Поясним сейчас только идею, с рассмотрением общего случая
☞
((:gruppe:galois#полиномы_над_gf_p ЗДЕСЬ)).
Пусть элемент $ \mathfrak a $ поля $ \mathbf{GF}(2^m) $ удовлетворяет уравнению $ f(\mathfrak x)=\mathfrak o $, где $ f_{}(x) $ --- полином над $ \mathbf{GF}(2) $. Тогда и $ \mathfrak a^2 $ --- тоже удовлетворяет этому уравнению. Действительно, если
$$ f(x)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n $$
то
$$ \left[ f(x) \right]^2 = a_0^2(x^2)^n+a_1^2(x^2)^{n-1}+\dots+a_{n-1}^2x^2+a_n^2+ 2 \sum_{0\le j
4.