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


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


Поле GF(64)

Факторизация полиномов

П

Пример. Разложить полином 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\}.


2013/02/14 22:57 редактировал au