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


Вспомогательная страница к разделу ПОЛЯ ГАЛУА.


Поле 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_{} множители приведено ЗДЕСЬ:

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_{}, который мы обозначим1) 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) \ .

Здесь проверка сохранения результатов сложения оказывается более простой, чем в предыдущем случае. Если2)

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

§

Подчеркнем то обстоятельство, что только что приведенное заключение будет справедливо при выборе в качестве \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 с двоичным представлением \quad (1011)

И это представление инвариантно относительно выбора примитивного элемента \mathfrak A — про него достаточно знать, что он существует, имеет порядок 15_{} и удовлетворяет равенству \mathfrak A^4 + \mathfrak A + \mathfrak e = \mathfrak o. Поскольку довольно часто это поле используется в примерах, приведенную выше таблицу переписал в терминах \mathfrak A ЗДЕСЬ.

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

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

1) Операция ^{\ast} описывается в ☞ ПУНКТЕ.
2) Обозначения аналогичны предыдущему случаю.

2015/12/10 20:04 редактировал au