Задача. Исследовать поле $ \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_{} $ множители приведено ☞ ЗДЕСЬ: $$ 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) $ и примитивного элемента $ \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) $. Теорема, приведенная в конце ☞ ПУНКТА, утверждает, что эти поля изоморфны, т.е. что между их элементами можно установить взаимно-однозначное соответствие, которое сохраняет результаты обеих операций — сложения и умножения. Проверим это. Изоморфизм первых двух полей устанавливается соответствием: $$ 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_{} $, который мы обозначим¹⁾ $ 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 $$ также будет неприводимым полиномом.

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, приведенной ☞ ЗДЕСЬ. Из этой же теоремы будет следовать и еще один факт, не такой очевидный при визуальном просмотре таблиц приведенного примера. При $ \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 ☞ ЗДЕСЬ ).

Совершенно аналогично проверяется, что в любом рассмотренном варианте поля $ \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} \} \ . $$

Будет ли справедливо общее утверждение, что корнями каждого из неприводимых полиномов является набор степеней некоторого элемента поля, или это только особенность рассмотренного примера ? — Да, будет. Поясним сейчас только идею, с рассмотрением общего случая ☞ ЗДЕСЬ. Пусть элемент $ \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<k\le n} a_ja_k x^{n-j}x^{n-k} \equiv_{2} $$ $$ \equiv_{2} a_0(x^2)^n+a_1(x^2)^{n-1}+\dots+a_{n-1}x^2+a_n \equiv f(x^2) \ . $$ Здесь $ a_j^2=a_j $ поскольку $ a_j \in \{0,1\} $. Таким образом, при $ f(\mathfrak a)=\mathfrak o $ будет и $ f(\mathfrak a^2)=\mathfrak o $; а уж из этого вытекает, что и $ f(\mathfrak a^4)=\mathfrak o,\ f(\mathfrak a^8)=\mathfrak o $ и т.д.

4. В чем заключается принципиальное отличие полинома $ f_3(x) $ от полиномов $ f_{1}(x) $ и $ f_2(x) $? — Все три полинома являются неприводимыми по модулю $ 2_{} $ полиномами $ 4_{} $-й степени; почему корни полинома $ f_3(\mathfrak x) $ не оказались примитивными элементами поля — в отличие от корней полиномов $ f_1(\mathfrak x) $ или $ f_2(\mathfrak x) $ ?

Дело в том, что полином $ f_3(x) $ оказывается делителем полинома $ x^5-1 $: $$ x^5-1 \equiv (x-1)(x^4+x^3+x^2+x+1) \ . $$ Любой корень полинома $ f_3(\mathfrak x) $ будет удовлетворять условию $ \mathfrak x^5 = \mathfrak e $, т.е. будет принадлежать показателю $ 5_{} $ (как это и наблюдалось в разобранном выше примере). Поэтому эти корни не могут принадлежать показателю $ 15_{} $, т.е. они не являются примитивными элементами поля $ \mathbf{GF}(16) $.

Неприводимый полином $ f_{}(x) $ над $ \mathbf{GF}(2) $ степени $ m_{} $ называется примитивным если он не является делителем полинома $ x^n-1 $ ни при каких $ n_{} $ меньших, чем $ 2^m-1 $. В разобранном примере полиномы $ f_{1}(x) $ и $ f_{2}(x) $ были примитивными.

Можно доказать (см. ☞ ЗДЕСЬ), что всегда корнями примитивных полиномов являются (исключительно) различные примитивные корни поля.