!!§!! Вспомогательная страница к разделу
☞
((:gruppe:galois#полиномы_неприводимые_по_модулю ПОЛЯ ГАЛУА)).
----
==Поле GF(64)==
~~TOC~~
===Факторизация полиномов==
!!П!! **Пример.** Разложить полином $ x^{64}-x $ на неприводимые по модулю $ 2_{} $ множители.
**Решение**. С помощью результатов пункта
☞
((:complex_num:circlediv УРАВНЕНИЕ ДЕЛЕНИЯ КРУГА)) раскладываем полином на неприводимые множители над $ \mathbb Z_{} $:
$$ x^{64}-x \equiv x(x-1)(x^2+x+1)(x^6+x^3+1)(x^6+x^5+x^4+x^3+x^2+x+1) \times $$
$$ \times \underbrace{(x^{12}-x^{11}+x^9-x^8+x^6-x^4+x^3-x+1)}_{X_{_{21}}(x)}\underbrace{(x^{36}-x^{33}+x^{27}-x^{24}+x^{18}-x^{12}+x^9-x^3+1)}_{X_{_{63}}(x)} \ . $$
Определяем количество неприводимых по модулю $ 2_{} $ полиномов степеней $ 6_{} $ и всех делителей этого числа:
$$ \xi(1)=2,\ \xi(2)=1,\ \xi(3)=2,\ \xi(6)=9 \ . $$
Неприводимые по модулю $ 2_{} $ полиномы степеней $ 1,2,3 $ уже построены в примерах
☞
((:gruppe:galois#полиномы_неприводимые_по_модулю ПУНКТА)):
$$ (x^6+x^5+x^4+x^3+x^2+x+1) \equiv (x^3+x^2+1)(x^3+x+1) \pmod 2 \ . $$
Полином $ x^6+x^3+1 $ должен быть неприводим по модулю $ 2_{} $, остальные $ 8_{} $ неприводимых по модулю $ 2_{} $ полиномов $ 6_{} $-й степени должны быть делителями полиномов $ X_{21}(x) $ и $ X_{63}(x) $. Полином $ X_{21}(x) $ является возвратным полиномом четной степени. Согласно теореме $ 5 $ из пункта
☞
((:polynomial:reciprocal ВОЗВРАТНЫЙ ПОЛИНОМ)), полином $ X_{21}(x) $ должен раскладываться над множеством $ \mathbb C_{} $ на два множителя $ 6_{} $-й степени:
$$ X_{21}(x) \equiv F(x)F^{\ast}(x) \ , $$
где
$$
\begin{matrix}
F(x)& \equiv & A_0x^6+A_1x^5+A_2x^4+A_3x^3+A_4x^2+A_5x+A_6,\\
F^{\ast}(x) & \equiv & A_0+A_1x+A_2x^2+A_3x^3+A_4x^4+A_5x^5+A_6x^6 \
\end{matrix}
$$
и $ \{ A_j\}_{j=0}^6 \subset \mathbb C $.
!!§!! В литературе по теории кодирования полином
$$ F^{\ast}(z)=A_0+A_1z+\dots+A_{n-1}z^{n-1}+A_nz^n $$
называется **полиномом, двойственным** к $ F(z)=A_0z^n+A_1z^{n-1}+\dots+A_{n-1}z+A_n $.
Попробуем применить этот же результат для факторизации полинома
$ X_{21}(x) $ по модулю $ 2_{} $, т.е. теперь будем искать $ \{ A_j\}_{j=0}^6 $ во множестве $ \{ 0,1 \} $. Из тождества
$$ X_{21}(x) \equiv F(x)F^{\ast}(x) \pmod{2} $$
сравнением коэффициентов при одинаковых степенях $ x_{} $ получаем систему сравнений:
$$ x^{12} : \quad
A_0A_6 \equiv 1 \pmod{2} \quad \Rightarrow \ A_0=1,A_6=1 \ ; $$
$$ x^{11} : \quad
A_0A_5+A_1A_6 \equiv 1 \pmod{2} \quad \Rightarrow \ A_1+A_5 \equiv 1 \pmod{2} \quad \Rightarrow \ A_1=1,A_5=0 $$
(или наоборот: $ A_1=0,A_5=1 $, но ввиду симметричности предполагаемого ответа, пренебрегаем этой альтернативой).
$$ x^{10} : \quad A_0A_4+A_1A_5+A_2A_6 \equiv 0 \pmod{2} \quad \Rightarrow \ A_2+A_4 \equiv 0 \pmod{2} $$
Здесь уже возможны две принципиально разные ситуации: $ A_2=A_4=0 $ или $ A_2=A_4=1 $. Посмотрим на следующее сравнение:
$$ x^{9} : \quad A_0A_3+A_1A_4+A_2A_5+A_3A_6 \equiv 1 \pmod{2} \quad \Rightarrow \ 2A_3+A_4 \equiv 1 \pmod{2} \quad \Rightarrow \ A_4 \equiv 1 \pmod{2} \ , $$
т.е. в предыдущем случае следует выбрать единственную возможность: $ A_2=A_4=1 $. Следующее сравнение позволит однозначно определить $ A_3 $:
$$ x^{8} : \quad \dots \quad \Rightarrow \ 1+A_3 \equiv 1 \pmod{2} \quad \Rightarrow \ A_3 \equiv 0 \pmod{2} \ ; $$
и окончательно: $ F(x) \equiv x^6+x^5+x^4+x^2+1 $. Проверка подтверждает справедливость сравнения
$$ X_{21}(x) \equiv (x^6+x^5+x^4+x^2+1)(x^6+x^4+x^2+x+1) \pmod{2} \ . $$
Что делать с полиномом $ X_{63}(x) $? Обратим внимание, что все его мономы являются степенями $ y=x^3 $. Делаем подстановку:
$$ X_{63}(x)\equiv y^{12}-y^{11}+y^9-y^8+y^6-y^4+y^3-y+1 $$
и получим уже исследованный ранее полином $ X_{21}(y) $. Таким образом,
$$ X_{63}(x)\equiv (y^6+y^5+y^4+y^2+1)(y^6+y^4+y^2+y+1)\pmod{2} \equiv $$
$$ \equiv (x^{18}+x^{15}+x^{12}+x^6+1)(x^{18}+x^{12}+x^6+x^3+1) \pmod{2} \ . $$
Оба сомножителя --- двойственные один другому, так что факторизация одного из них позволит факторизовать и второй. Рассмотрим первый:
$$ x^{18}+x^{15}+x^{12}+x^6+1 \equiv (x^{18}+x^{12}+x^6+1)+x^{15} \equiv_{_{2}} (x^6+1)^3+x^{15}
\equiv_{_2} (x^6+x^5+1)(x^{12}+x^{11}+x^{10}+x^5+1) \ . $$
Из получившихся сомножителей первый должен быть неприводимым полиномом, а второй факторизуется подборкой:
$$ x^{12}+x^{11}+x^{10}+x^5+1 \equiv_{_2} (x^6+x^5+x^2+x+1)(x^6+x^4+x^3+x+1) \ . $$
Аналогично:
$$ x^{18}+x^{12}+x^6+x^3+1 \equiv_{_2} $$
$$ \equiv_{_2} (x^6+x+1)(x^{12}+x^{7}+x^2+x+1) \equiv_{_2} (x^6+x+1)(x^6+x^5+x^4+x+1)(x^6+x^5+x^3+x^2+1) \ .
$$
♦
!!П!! **Пример.** Найти примитивные полиномы степени $ 6_{} $ над $ \mathbf{GF}(2) $.
**Решение.** В соответствии со следствием $ 1 $ к теореме $ 2 $
☞
((:gruppe:galois#полиномы_над_gf_p ЗДЕСЬ)), количество примитивных полиномов равно $ \phi(2^6-1)/6=6 $ (здесь $ \phi $ --- ((:numtheory#функция_эйлера функция Эйлера)) ). В соответствии со следствием 2 к той же теореме, полином будет примитивным степени $ 6_{} $ если он не является делителем полиномов $ x^{21}-1 $ и $ x^{9}-1 $. Проверка показывает, что полином
$$ f_{6,1}(x)=x^6+x^3+1 $$
является делителем $ x^9-1 $, а полиномы
$$f_{6,2}(x)=x^6+x^5+x^4+x^2+1 \quad u \quad f_{6,2}^{\ast}(x)=x^6+x^4+x^2+x+1 $$
--- делителями полинома $ x^{21}-1 $. Остальные $ 6_{} $ полиномов, полученных в предыдущем примере
$$ f_{6,3}(x)=x^6+x^5+1, \quad f_{6,3}^{\ast}(x)=x^6+x+1\ ; $$
$$ f_{6,4}(x)=x^6+x^5+x^2+x+1, \quad f_{6,4}^{\ast}(x)=x^6+x^5+x^4+x+1\ ; $$
$$ f_{6,5}(x)=x^6+x^4+x^3+x+1, \quad f_{6,5}^{\ast}(x)=x^6+x^5+x^3+x^2+1 $$
являются примитивными.
Показатели, которым принадлежат неприводимые делители полинома $ x^{63}-1 $, приведены в таблице:
$$
\begin{array}{c|c|l}
x+1 & 1 & \\
\hline
x^2+x+1 & 3 & \mathfrak A^{21} \\
\hline
x^3+x^2+1; \ x^3+x+1 & 7 & \mathfrak A^{9} \\
\hline
f_{6,1}(x) & 9 & \mathfrak A^{7} \\
f_{6,2}(x);\ f_{6,2}^{\ast}(x) & 21 & \mathfrak A^{3} \\
f_{6,3}(x);\ f_{6,3}^{\ast}(x) & 63 & \\
f_{6,4}(x);\ f_{6,4}^{\ast}(x) & 63 & \\
f_{6,5}(x);\ f_{6,5}^{\ast}(x) & 63 & \\
\end{array}
$$
Последний столбец содержит степень примитивного элемента поля, являющуюся корнем одного из полиномов, стоящих в той же строке. Так, к примеру, если через $ \mathfrak A $ обозначен корень полинома $ f_{6,3}(x) $, то из условия $ \mathfrak A^6+\mathfrak A^5+1= \mathfrak o $ следует $ (\mathfrak A^9)^3+\mathfrak A^9+1= \mathfrak o $, т.е. что $ \mathfrak A^9 $ является корнем полинома $ x^3+x+1 $.
В соответствии с теоремой 1, приведенной
☞
((:gruppe:galois#полиномы_над_gf_p ЗДЕСЬ)), оставшиеся корни полинома $ x^3+x+1 $ представляют собой $ \mathfrak A^{18} $ и $ \mathfrak A^{36} $. Аналогичное заключение справедливо и для всех остальных неприводимых полиномов. И это обстоятельство позволяет построить __все__ примитивные полиномы если найден хотя бы один.
===Поиск примитивных полиномов с помощью преобразования Чирнгауза==
!!§!! Грубый набросок теории, которую когда-нибудь надо будет выписать аккуратно.
Допустим, что в случае примера предыдущего пункта, нам удалось найти один примитивный полином --- именно $ f_{6,3}(x)=x^6+x^5+1 $. Если $ \mathfrak A $ --- какой-то его корень, то, в соответствии с теоремой 1, приведенной ((:gruppe:galois#полиномы_над_gf_p ЗДЕСЬ)), множество его корней совпадает с
$ \mathfrak A, \mathfrak A^2, \mathfrak A^4, \mathfrak A^8, \mathfrak A^{16}, \mathfrak A^{32} $. Корнем любого другого неприводимого полинома будет некоторая степень примитивного элемента, скажем, $ \mathfrak A^j $. Тогда все множество корней, в соответствии с упомянутым результатом, будет совпадать с $ \mathfrak A^j, \mathfrak A^{2j}, \mathfrak A^{4j}, \mathfrak A^{8j}, \mathfrak A^{16j}, \mathfrak A^{32j} $ --- хотя и не все элементы этого набора будут различными, но других корней точно не будет! Получается, что корнями неприводимого полинома оказываются $ j_{} $-е степени корней примитивного полинома.
В теории полиномов над бесконечными полями разработан аппарат построения по заданному полиному $ f_{}(x) $ с корнями, обозначенными $ \lambda_1,\lambda_2,\dots $, нового полинома $ F_{}(y) $ корнями которого являются $ g(\lambda_1),g(\lambda_2),\dots $ при заданном полиноме $ g_{}(x) $; такое преобразование $ f(x) \mapsto F(y) $ называлось ((:polynomial:radical#преобразование_чирнгауза преобразованием Чирнгауза)). Алгоритм, основанный на детерминантном представлении результанта, позволяет получить полином $ F_{}(y) $ в явном виде и с целыми коэффициентами, если исходный полином $ f_{}(x) $ и полином $ g_{}(x) $ также имеют целые коэффициенты; т.е. собственно выражения для корней $ f_{}(x) $ можем и не знать!
Перетащим эти наработки в конечные поля; из различных детерминантных представлений преобразования Чирнгауза возьмем метод Эрмита. Преобразование Чирнгауза полинома $ x^6+x^5+1 $ при выборе
$ g(x)\equiv x^5 $ дает
$$F(y)=y^6+y^5+5\,y^4+10\,y^3+10\,y^2+5\,y+1 \equiv_{_2} y^6+y^5+y^4+y+1 \ , $$
т.е., с точностью до переобозначения переменной, примитивный полином $ f_{6,4}^{\ast} $ из предыдущего пункта. Далее:
$$ y=x^{11} \Rightarrow f_{6,5},\ y=x^{13} \Rightarrow f_{6,5}^{\ast},\ y=x^{23} \Rightarrow f_{6,4},\ y=x^{31} \Rightarrow f_{6,3}^{\ast} \ . $$
Тут отдельно надо описать правило выбора степеней в преобразовании Чирнгауза (чтобы получались именно примитивные полиномы), но мне сейчас некогда. Метод "достаточно умён" --- посмотрите, что получается при выборе $ g(x)\in \{x^2,x^3,x^7,x^9\} $.