Пример. Разложить полином $ x^{64}-x $ на неприводимые по модулю $ 2_{} $ множители.

Решение. С помощью результатов пункта ☞ УРАВНЕНИЕ ДЕЛЕНИЯ КРУГА раскладываем полином на неприводимые множители над $ \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 $ уже построены в примерах ☞ ПУНКТА: $$ (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 $ из пункта ☞ ВОЗВРАТНЫЙ ПОЛИНОМ, полином $ 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 $ ☞ ЗДЕСЬ, количество примитивных полиномов равно $ \phi(2^6-1)/6=6 $ (здесь $ \phi $ — функция Эйлера ). В соответствии со следствием 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, приведенной ☞ ЗДЕСЬ, оставшиеся корни полинома $ x^3+x+1 $ представляют собой $ \mathfrak A^{18} $ и $ \mathfrak A^{36} $. Аналогичное заключение справедливо и для всех остальных неприводимых полиномов. И это обстоятельство позволяет построить все примитивные полиномы если найден хотя бы один.

Грубый набросок теории, которую когда-нибудь надо будет выписать аккуратно.

Допустим, что в случае примера предыдущего пункта, нам удалось найти один примитивный полином — именно $ f_{6,3}(x)=x^6+x^5+1 $. Если $ \mathfrak A $ — какой-то его корень, то, в соответствии с теоремой 1, приведенной ЗДЕСЬ, множество его корней совпадает с $ \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) $ называлось преобразованием Чирнгауза. Алгоритм, основанный на детерминантном представлении результанта, позволяет получить полином $ 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\} $.