Полета на Галоа или крайни полета

Алексей Юрьевич Утешев § В този раздел буквата p означава просто число.

Структура на крайно поле

Существуването на крайни полета, т.е. полета състоящи се от краен брой елементи е установено в раздела ПОЛЕ. П Пример. Множество то от $\mathbb Z_{p}$ класовете остатъци по прост модул p образуват поле относно операциите събиране и умножение.
Да разгледаме сега едно крайно поле от най-общ вид. Всяко такова поле $\mathbb F_{}$ трябва да съдържа неутрални елементи по отношение на събирането и умножението: $\mathfrak o$ — нулев и $\mathfrak e$ — единичен.
Да започнем последователно да събираме единичните елементи $\mathfrak a_1= \mathfrak e,\ \mathfrak a_2=\mathfrak e+\mathfrak e,\ \mathfrak a_3=\mathfrak e+\mathfrak e+\mathfrak e,\dots$
Понеже, по допускане, полето съдържа само краен брой елементи, то елементите от редицата $\{\mathfrak a_j\}_{j\in \mathbb N}$ трябва да се повтарят.
Ако $\mathfrak a_k= \mathfrak a_{\ell}$ при $k<\ell$ , то $\mathfrak a_{\ell-k}= \mathfrak a_{\ell}-\mathfrak a_k = \mathfrak o \ .$
Така че, в разглежданата редица непременно ще се срещнат нулеви елементи. Т Теорема 1. Нека първият нулев елемент от редицата $\{\mathfrak a_j\}$ има номер $M_{}$ : $\mathfrak a_M=\mathfrak o, \mathfrak a_j \ne \mathfrak o \quad npu \quad j\in \{1,\dots,M-1\} .$ Числото $M_{}$ е просто.
Всички елементи $\mathfrak a_1,\dots,\mathfrak a_{M-1}$ са различни.
Доказателство.
∇ Ако $M_{}$ е съставно:

при

, то $\mathfrak o=\mathfrak a_M=\mathfrak a_{M_1}\cdot \mathfrak a_{M_2} \ .$
И двата елемента $\mathfrak a_{M_1}$ и $\mathfrak a_{M_2}$ по предположение, са ненулеви, а тяхното произведение е нулевият елемент.
Но това противоречи на свойствата на полето.
Останалото твърдение докажете самостоятелно. ⟩
Простото число $M=p_{}$ от предната теорема се нарича характеристика на крайното поле. Т Теорема 2. Редът ( броят на елементите ) на произволно, крайно поле е равен на някоя степен на неговата характеристика:
$\operatorname{Card} (\mathbb F) = p^m \quad$ при p - просто и $\quad m \in \mathbb N \ .$
Доказателство.
∇ В предишната теорема беше доказано, че крайното поле $\mathbb F$ с характеристика p съдържа поне p различни елемента: $\mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_{p-1} \quad npu \quad \mathfrak a_j= \underbrace{\mathfrak e + \dots+ \mathfrak e}_{j} \ .$
Това множество притежава всички свойства на поле и е изоморфно на полето $\mathbb Z_p$ .
Изоморфизмът се установява чрез соответствието $\mathfrak a_j \mapsto \overline j$ .
Наистина , по допускане $\mathfrak a_p= \mathfrak o$ , но тогава $\mathfrak a_{p+1}= \mathfrak a_1, \mathfrak a_{p+2}= \mathfrak a_2, \dots , \mathfrak a_{p+j}= \mathfrak a_j, \dots ,$ и следователно, $\mathfrak a_j+ \mathfrak a_k=\mathfrak a_{j+k}=\mathfrak a_{ j+k \pmod{p}}$ .
Така че $\mathfrak a_j+ \mathfrak a_k \mapsto \overline{j +k}$ , т.е. съответствието запазва резултата от събирането.
Резултатът от умноженито също се запазва, защото от свойствата на полето (в частност, от дистрибутивността на умноженито относно събирането), следва $\mathfrak a_j \cdot \mathfrak a_k=\mathfrak a_{jk} = \mathfrak a_{jk \pmod{p}} \ ,$ т.е. $\mathfrak a_j \cdot \mathfrak a_k \mapsto \overline{jk}$ .
Установеният изоморфизм ни дава основание да твърдим, че всеки елемент $\mathfrak a_j \ne \mathfrak o$ има обратен сред това множество: $\mathfrak a_{j}^{-1} = \mathfrak a_{s}$ , където $s_{}$ — числото, е обратно $j_{}$ по отношение умножението по модул p
Ако в полето $\mathbb F$ няма други елементи, то $\mathbb F = \{ \mathfrak a_j \}_{j=0}^{p-1}$ и теоремата е доказана: $\operatorname{Card} (\mathbb F) = p$ .
Да предположим, че съществува $\mathfrak A \in \mathbb F$ и $\mathfrak A \not\in \{ \mathfrak a_j \}_{j=0}^{p-1}$ .
Тогава множеството $\{\mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \}_{j,k=0}^{p-1}$ определя

различни елементи на полето $\mathbb F$ .
Наистина, ако $\mathfrak a_{j_{_1}}+ \mathfrak a_{k_{_1}} \cdot \mathfrak A = \mathfrak a_{j_{_2}}+ \mathfrak a_{k_{_2}} \cdot \mathfrak A ,$ то $\quad \mathfrak a_{j_{_1}}- \mathfrak a_{j_{_2}}=(\mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}}) \mathfrak A \ .$
Ако $\mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}} \ne \mathfrak o$ , то, по доказаното преди, съществува обратен на елемента $\mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}}$ и този елемент се съдържа в множеството $\{ \mathfrak a_j \}_{j=1}^{p-1}$ .
Тогава от последното равенство следва, че $\mathfrak A=(\mathfrak a_{k_{_2}}-\mathfrak a_{k_{_1}})^{-1} (\mathfrak a_{j_{_1}}- \mathfrak a_{j_{_2}}) \quad \Rightarrow \quad \mathfrak A \in \{ \mathfrak a_j \}_{j=0}^{p-1} \ ,$ което противоречи на предположението.
Ако $\mathfrak a_{k_{_2}}- \mathfrak a_{k_{_1}} = \mathfrak o$ , то тогава и $\mathfrak a_{j_{_1}}-\mathfrak a_{j_{_2}} = \mathfrak o$ .
Ако в полето $\mathbb F$ няма други елементи, то $\mathbb F =\{ \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A \}_{j,k=0}^{p-1}$ и $\operatorname{Card} (\mathbb F) = p^2$ .
В противен случай, съществува елемент $\mathfrak B_{}$ , който не се съдържа в това подмножество, и ще разгледаме множеството $\{ \mathfrak a_j+ \mathfrak a_k \cdot \mathfrak A + \mathfrak a_{\ell} \cdot \mathfrak B \}_{j,k,\ell=0}^{p-1} \ ,$ което определя

различни елемента от полето $\mathbb F$ .
По-нататъшният ход на доказателството е аналогичен на предишните разсъждения.
Понеже, по допускане, броят на елементите на полето е краен, то процесът е длъжен да приключи след краен брой стъпки и ако последната има номер $m_{}$ , ще получим твърдението на теоремата. ⟩ П Пример. Да разгледаме поле, съдържащо $4_{}$ -х елемента. Два от тях — това са неутралните елементи $\mathfrak o$ и $\mathfrak e$ .
Останалите два да означим с $\mathfrak a$ и $\mathfrak b$ .
Да се опитаме да запищем за тези елементи таблиците за събиране и умножение, водени единствено от определението за поле
Да започнем със събирането.
Понеже характеристиката на полето е равна на p = 2 получаваме $\mathfrak e + \mathfrak e = \mathfrak o \ .$
На какво може да е равна сумата $\mathfrak a+ \mathfrak e$ ?
Ако $\mathfrak a+ \mathfrak e= \mathfrak o$ , то, прибавяйки към двете чести на равенството $\mathfrak e$ , от предното равенство, получаваме $\mathfrak a = \mathfrak e$ , което противоречи на предположението, че $\mathfrak a$ е различен от нула $\mathfrak o$ и $\mathfrak e$ .
По подобен начин се доказва и невъзможността на равенството $\mathfrak a+ \mathfrak e= \mathfrak e$ — то води до заключението, че $\mathfrak a = \mathfrak o$ .
Нека сега $\mathfrak a+ \mathfrak e= \mathfrak a$ .
Основавайки се на аксиомите на полето , за елемента $\mathfrak a$ трябва да съществува противоположен относно събирането; ние засега не знаем на какво е равен, но знаем, че той съществува.
Да го означим с $x_{}$ , тогава $\mathfrak a +x = \mathfrak o$ .
Да прибавим този елемент към двете страни на равенство $\mathfrak a+ \mathfrak e= \mathfrak a$ . Получаваме $\mathfrak e= \mathfrak o$ , което е невъзможно.
Остава само един възможен вариант: $\mathfrak a+ \mathfrak e= \mathfrak b$ . Оттук се получава и второто равенство: $\mathfrak b+ \mathfrak e= \mathfrak a$ .
И така, таблица за събиране ( взимайки предвид разместително свойство ) е донякъде запълнена: $\begin{array}{r|rrrr} \mathbb{+} & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \hline \mathfrak o & \mathfrak o & \mathfrak e & \mathfrak a & \mathfrak b \\ \mathfrak e & \mathfrak e & \mathfrak o & \mathfrak b & \mathfrak a \\ \mathfrak a & \mathfrak a & \mathfrak b & & \\ \mathfrak b & \mathfrak b & \mathfrak a & & \end{array}$ Да се опитаме да попълним останалите места. На какво може да е равна сумата $\mathfrak a+ \mathfrak a$ ?
Равенството $\mathfrak a+ \mathfrak a = \mathfrak a$ е невъзможно, защото от него би следовало, че $\mathfrak a = \mathfrak o$ .
Ако $\mathfrak a+ \mathfrak a = \mathfrak b$ , то прибавяйки към двете страни на равенството $\mathfrak e$ ще получим ( с използване на вече запълнените части на таблицата ), че $\mathfrak a+ \mathfrak b = \mathfrak a$ , което отново довежда към противореччието $\mathfrak b = \mathfrak o$ .
Нека $\mathfrak a+ \mathfrak a = \mathfrak e$ . За доказателството на противоречивостта на това равенство се налага да използваме операцията умножение. От аксиомите на поле, имаме: за елемента $\mathfrak a$ существува обратен относно умножението. Ние, засега не знаем, на какво той е равен, но знаем, че той съществува. Да го означим с $y_{}$ , тогава $\mathfrak a \cdot y = \mathfrak e$ . Да умножим равенството $\mathfrak a+ \mathfrak a = \mathfrak e$ с $y_{}$ . Като използваме аксиомите на поле достигаме до $\mathfrak e+ \mathfrak e = y$ , откъдето $y= \mathfrak o$ , което е невъзможно.
Остава един единствен вариант: $\mathfrak a+ \mathfrak a = \mathfrak o$ . С такива разсъждения доказваме и че $\mathfrak b+ \mathfrak b = \mathfrak o$ .
Остава да намерим $\mathfrak a+ \mathfrak b$ . Тази сума не може да е равна нито на $\mathfrak a$ , нито на $\mathfrak b$ , защото по допускане, $\mathfrak a \ne \mathfrak b$ . Равенството $\mathfrak a+ \mathfrak b = \mathfrak o$ също е невъзможно, защото прибавяйки към двете му части $\mathfrak a$ , и използвайки резултата от преди , достигаме до същото противоречие: $\mathfrak a = \mathfrak b$ . Така че единствения оставащ вариант е: $\mathfrak a+ \mathfrak b = \mathfrak e$ .
Окончателно таблицата на събирането придобива вида: Таблица на събирането

Сега да се заемем с умножението. Началото е лесно: Таблица на умножението

На какво е равно произведението $\mathfrak a \cdot \mathfrak a$ ? Вариантът $\mathfrak a \cdot \mathfrak a = \mathfrak o$ отпада, понеже от него ( с умножаване на обратния относно умножението ) следва $\mathfrak a = \mathfrak o$ . Да забележим, че на същото основание, $\mathfrak b \cdot \mathfrak b \ne \mathfrak o \ .$
От варианта $\mathfrak a \cdot \mathfrak a = \mathfrak a$ следва, че $\mathfrak a = \mathfrak e$ , което също е невозможно. Возможно ли е, да бъде $\mathfrak a \cdot \mathfrak a = \mathfrak e$ , т.е. елементът $\mathfrak a$ да е обратен на самия себе си? С помощта на таблицата за събиране получаваме веригата от следствия:

последното противоречи на предишното неравенство. И така, произведението $\mathfrak a \cdot \mathfrak a$ може да бъде само $\mathfrak b$ . Аналогично се доказва, че $\mathfrak b \cdot \mathfrak b$ може да бъде единствено $\mathfrak a$ . Накрая, $\mathfrak a \cdot \mathfrak b = \mathfrak a \cdot (\mathfrak a+\mathfrak e) = \mathfrak a \cdot \mathfrak a + \mathfrak a = \mathfrak b + \mathfrak a = \mathfrak e \ .$
Окончателно: Таблица на умножението

⟩
И така тези разсъждения ни водят до извода: ако существува крайно поле от $4_{}$ елемента, то в него операциите събиране и умножения трябва да се извършват по единствено возможните начини, които се описват с получените таблици.
Но остава открит въпроса: Няма ли противоречие в така построените таблици?
Възможно е да съществува пропусната от нас последователност от действия, която ще доведе до противоречие.
Отговорът на този въпрос се оказва отрицателен: противоречие няма да получим. П Пример. Да разгледаме множеството , состоящо се от квадратните матрици от втори ред $\mathfrak o= \left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \end{array} \right),\ \mathfrak e= \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right),\ \mathfrak a= \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right),\ \mathfrak b= \left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right).$ В това множество операцията събиране да определим като събиране на матрици но по модул 2: $\left(\begin{array}{ll} a_{11}& a_{12} \\ a_{21}&a_{22} \end{array} \right)+ \left(\begin{array}{ll} b_{11}& b_{12} \\ b_{21}&b_{22} \end{array} \right)= \left(\begin{array}{ll} a_{11}+b_{11} \pmod{2} & a_{12}+b_{12} \pmod{2} \\ a_{21}+b_{21} \pmod{2} & a_{22}+b_{22} \pmod{2} \end{array} \right)$ а операцията умножение — като съответната при матриците, но също по модул 2, т.е.: $\left[\begin{array}{ll} a_{11}& a_{12} \\ a_{21}&a_{22} \end{array} \right]\times \left[\begin{array}{ll} b_{11}& b_{12} \\ b_{21}&b_{22} \end{array} \right] \left(\begin{array}{ll} a_{11}b_{11} +a_{12}b_{21} \pmod{2} & a_{11}b_{12} +a_{12}b_{22} \pmod{2} \\ a_{21}b_{11} +a_{22}b_{21} \pmod{2} & a_{21}b_{12} +a_{22}b_{22} \pmod{2} \end{array} \right) \ .$ Можем да проверим, че таблиците на действията с елементите на това множество съвпадат с таблиците, приведени по-горе. ⟩
По - нататък ще бъде приведен пример на крайно поле от ред $p^{m}$ . То се нарича поле на Галоа и се означава с $\mathbf{GF}(p^m)$ .

Обобщена теорема на Ферма

Т Теорема. Всеки елемент $\mathfrak a \in \mathbf{GF}(p^m)$ удовлетворява равенството $\mathfrak a^{p^m} - \mathfrak a = \mathfrak o \ .$
Доказателството е аналогично на доказателството малка теорема на Ферма.
∇ Да означим за краткост

, и да разгледаме множеството от всички ненулеви елементи полето $\mathfrak a_1,\dots, \mathfrak a_{q-1} \ .$
Ако $\mathfrak a \ne \mathfrak o$ , е произволен елемент от това множество да умножим елементите на множеството с него: $\mathfrak a \mathfrak a_1,\dots, \mathfrak a \mathfrak a_{q-1} \ .$ Получават се елементи от полето. Те всички са различни от $\mathfrak o$ (понеже в полето не существуват делители на нула) и всички са различни помежду си: $\mathfrak a \mathfrak a_j = \mathfrak a \mathfrak a_k \quad \Rightarrow \quad \mathfrak a (\mathfrak a_j - \mathfrak a_k)= \mathfrak o \quad \Rightarrow \quad \mathfrak a = \mathfrak o \quad$ или $\quad \mathfrak a_j = \mathfrak a_k \ .$ Следователно множеството $\{ \mathfrak a \mathfrak a_j \}_{j=1}^{q-1}$ съвпада с множеството $\{ \mathfrak a_k \}_{k=1}^{q-1}$ . Но тогава произведението на елементите на тези множеста са равни: $\prod_{j=1}^{q-1} (\mathfrak a \mathfrak a_j) = \prod_{j=1}^{q-1} \mathfrak a_j \quad \Rightarrow \quad a^{q-1} \prod_{j=1}^{q-1} \mathfrak a_j = \prod_{j=1}^{q-1} \mathfrak a_j \ .$ Произведение от ненулеви елементи на поле е различно от $\mathfrak o$ , следователно $\mathfrak a^{q-1}= \mathfrak e \ ;$ . Това равенство е вярно за всеки ненулев елемент от полето. Умножавайки го на $\mathfrak a$ , получаваме равенството от условието на теоремата, което ще се удовлетворява и за $\mathfrak a = \mathfrak o$ . ⟩ Т Теорема. Всеки елемент $\mathfrak a \in \mathbf{GF}(p^m)$ удовлетворява равенство от вида: $\mathfrak a^m + A_1 \mathfrak a^{m-1} + \dots + A_{m} = \mathfrak o \quad npu \quad \{ A_1,\dots,A_m \} \subset \{ \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_{p-1} \},\ \mathfrak a_{j}= \underbrace{\mathfrak e+\dots+\mathfrak e}_{j}, \quad u \quad m \in \mathbb N \ .$
Ще наричаме уравнение от вида $\mathfrak x^m + A_1 \mathfrak x^{m-1} + \dots + A_{m} = \mathfrak o$ при $\{ A_1,\dots,A_m \} \subset \{ \mathfrak a_0=\mathfrak o, \mathfrak a_1,\dots,\mathfrak a_{p-1} \}$ алгебраично уравнение в $\mathbf{GF}(p^m)$ от степен $m_{}$ с неизвестно $\mathfrak x_{}$ . Коефициентите му са аналог на целите числа.
Доказателство.
∇ При доказателството теорема 2 от предишния пункт бе показано, че във всяко поле $\mathbb P$ ще се намерят $m_{}$ елемента $\mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m$ , такива, че всеки елемент от полето може да се представи като линейна комбинация с коефициенти от множеството $\{ \mathfrak a_{j} \}_{j=0}^{p-1}$ .
Да изразим като линейна комбинация елементите $\mathfrak a, \mathfrak a \mathfrak A_1, \mathfrak a \mathfrak A_2,\dots, \mathfrak a \mathfrak A_m$ : $\begin{array}{lcl} \mathfrak a &=& A_{11} +A_{12} \mathfrak A_2+\dots+ A_{1m} \mathfrak A_m, \\ \mathfrak a \mathfrak A_2 &=& A_{21} +A_{22} \mathfrak A_2+\dots+ A_{2m} \mathfrak A_m, \\ \dots & & \dots \\ \mathfrak a \mathfrak A_m &=& A_{m1} +A_{m2} \mathfrak A_2+\dots+ A_{mm} \mathfrak A_m, \end{array} \qquad npu \quad \{ A_{jk} \}_{j,k=1}^m \subset \{ \mathfrak a_{j} \}_{j=0}^{p-1} \ .$ Да запишем тези уравнения като система: $\begin{array}{cccccc} (A_{11}- \mathfrak a) & +A_{12} \mathfrak A_2 & +\dots & + A_{1m} \mathfrak A_m &=& \mathfrak o, \\ A_{21} & +(A_{22}- \mathfrak a) \mathfrak A_2 &+\dots & + A_{2m} \mathfrak A_m &=& \mathfrak o, \\ \dots & & & & & \dots \\ A_{m1} & + A_{m2} \mathfrak A_2 & +\dots+ & (A_{mm}- \mathfrak a) \mathfrak A_m &=& \mathfrak o. \end{array}$ Системата уравнения, разглеждана спрямо елементите на полето $\mathfrak A_1=\mathfrak e, \mathfrak A_2,\dots, \mathfrak A_m$ е ленейна и хомогенна.

§ На това място ще се възползваме от подобието на задачата с тази за решаване на система от линейни уравнения с коефициенти от множеството $\mathbb Z_{}$ . Условията за разрешимост на такива системи могат да се формулират чрез детерминанти — т.е. многочленни функции от коефициентите на системата. Аналогията на този обект за крайно поле е очевидена и той е принципиално изчислим — понеже неговото формално определение използва само операциите събиране и умножение на елементи от полето.
Но детайлите на този пренос на резултатите от безкрайно множество $\mathbb Z_{}$ в крайно поле $\mathbb F_{}$ оставям неосветен

Понеже тази хомогенна система има ненулево решение ( $\mathfrak A_1=\mathfrak e\ne \mathfrak o$ ), нейната детерминанта трябва да е равна на нулевия елемент на полето: $\left|\begin{array}{cccc} A_{11}- \mathfrak a & A_{12} & \dots & A_{1m} \\ A_{21} & A_{22}- \mathfrak a& \dots & A_{2m} \\ \dots & & & \dots \\ A_{m1} & A_{m2}& \dots & A_{mm}- \mathfrak a \end{array} \right|= \mathfrak o \ .$ Детерминантата в лявата част се явява многочлен на $\mathfrak a$ от степен $m_{}$ с коефициенти, които са многочлени от величините $\{ A_{jk} \}_{j,k=1}^m$ , т.е., в крайна сметка, от $\{ \mathfrak a_{j} \}_{j=0}^{p-1}$ . ⟩
Да обобщим: елемент $\mathfrak a$ от полето $\mathbf{GF}(p^m)$ трябва да удовлетворява едновременно две алгебраични уравнения в това поле: $\mathfrak x^{p^m}- \mathfrak x = \mathfrak o$ и уравнене от вида $\mathfrak x^m + A_1 \mathfrak x^{m-1} + \dots + A_{m} = \mathfrak o$ от степен $m_{}$ .
Ако бихме имали работа с обикновени алгебрични уравнения с една променлива с цели коефициенти, то бихме могли да направим заключение за существуването на зависимост между коефициентите на тези уравнения във вид на алгебрично равенство (виж. → РЕЗУЛТАНТА ).
В случай на крайно поле, може да се направи по-дълбокият извод: вторият многочлен се оказва делител на първия.
Остана само да изведем операцията деление на многочлени в крайно поле, към което и пристъпваме.

Пример на крайно поле

Полиномът $F_{}(x)$ с цели коефициенти се нарича неприводим по модул p ако той не може да се представи във вида $F(x)\equiv F_1(x)F_2(x)+ p G(x) \ ,$ където

са многочлени с цели коефициенти и $\deg F_1 < \deg F, \deg F_2< \deg F$ .
В противен случай ще казваме, че многочленът $F_{}(x)$ е приводим по модул p или че $F_{}(x)$ се дели на

по модул p, или че

се явава делител $F_{}(x)$ по модул p.
Очевидно е, че ако многочленът $F(x) \in \mathbb Z[x]$ е приводим в $\mathbb Z_{}$ , то той е приводим и по произволен модул p. П Пример. Приводим ли е многочленът $2\,x^2+2\,x+1$ по модул $5_{}$ ?
∇ Този многочлен е неприводим $\mathbb Z_{}$ .
И въпреки това по модул $5_{}$ той се разлага на линейни множители, единият от които се открива чрез полагането $x_{}=1$ : $2\,x^2+2\,x+1\equiv (x-1)(2\,x+4)+5 \equiv (x-1)(2\,x+4) \pmod 5 \equiv$

⟩ П Пример. Приводим ли е многочленът $2\,x^2+2\,x-1$ по модул $5_{}$ ?
∇ Да разгледаме всевозможните комбинации от възможните линейни множители с коефициент от множеството $\{-2,-1,0,1,2\}$ : $2\,x\pm 1,\ 2\,x\pm 2,\ x\pm 2,\ x\pm 1 \ .$ Нито една двойка при умножаване не дава искания многочлен.
Отговор. Не. ? Да разгледаме нормализираният многочлен (т.е. със старши коефициент равен на 1 ) $f_{}(x)$ от степен $n_{}\ge 1$ с цели коефициенти. $f(x)=x^n+a_1x^{n-1}+\dots+a_n \in \mathbb Z[x] \ .$ Докажете, че частното и остатъкът от делението на произволен многочлен $g_{} (x)\in \mathbb Z[x]$ с $f_{}(x)$ ще бъдат многочлени с цели коефициенти. Подсказване : см. Доказателство на теоремата е → ТУК. !
Навсякъде в този пункт $f_{} (x)$ се предполага нормализиран и $\deg f \ge 1$ .
Полиномите $\{F_1(x),F_2(x)\} \subset \mathbb Z[x]$ се наричат сравними по двоен модул

ако тяхната разлика може да бъде представена във вида: $F_1(x)-F_2(x) \equiv p\cdot G(x) + f(x) H(x) \quad npu \quad \{G(x),H(x) \}\subset \mathbb Z[x] \ .$ С други думи, остатъкът от деленито

на $f_{}(x)$ предсатвлява многочлен, всички коефициенти на който са кратни на p: $\left( F_1(x)-F_2(x) \pmod{f(x)} \right) \pmod{p} \equiv 0 \ ;$ тук знакът $\equiv_{}$ означава тъждествено равенство.
В източника [3] за това понятие се използва нагледното означение $F_1(x)\equiv F_2(x) \quad (\operatorname{modd} \ p,f(x)) \ ,$ . П Пример. Намерете всички стойности на параметъра $\alpha \in \mathbb Z$ , при които полиномът $F_1(x)=7\,x^3+4\,x^2-x-3 \quad u \quad F_2(x)=3\,x^3-5\,x^2+\alpha\, x+7$ ще бъдат сравними по двоен модул $5,\, x^2+x+2$ .
∇ Да разделим

на

: $F_1(x)-F_2(x) \equiv (4\,x+5)(x^2+x+2)+((-14-\alpha)\,x-20) \ .$
Остатъкът от делението е равен на $(-14-\alpha)\,x-20$ , по модул $5_{}$ той е сравним с $(1-\alpha)\, x$ .
Коефициентът пред $x_{}$ се дели на $5_{}$ само при условие $\alpha \equiv 1 \pmod 5$ .
Отговор. $\alpha \equiv 1 \pmod 5$ .

Ще използваме означението $F(x)= F_1(x) \quad (\operatorname{modd} \ p,f(x))$ в същия смисъл, като в раздела → МОДУЛЯРНА АРИТМЕТИКА е исползвано означението $x = A \pmod{M}$ , т.е. на многочленът $F_{}(x)$ се присвоява остаткът от делението на

на $f_{}(x)$ , в който допълнително се заместват коефициентите му с техните остатъци от делението на p.

П Пример. За $F_1(x)=5\,x^4-x^2+x-4, f(x)= x^3+2\,x^2+3\,x-6$ и

имаме: $F_1(x)\equiv (5\,x-10)f(x) +4\,x^2+61\,x-64 \quad \Rightarrow \quad F(x)=4\,x^2+5\,x+6 \equiv F_1(x) \quad (\operatorname{modd} \ 7,f(x)) \ .$ Т Теорема. Нека $f_{}(x)$ — нормализиран, неприводим по модул p многочлен от степен $m\ge 1$ . Множеството $\mathbb P_{p,f} = \{ F (x)=A_0+A_1x+\dots+A_{m-1}x^{m-1} \ \mid \ \{A_0,A_1,\dots,A_{m-1}\} \subset \{0,1,\dots,p-1 \} \} \ ,$ с въведени в него операции събиране по модул p: $F_1(x)+F_2(x) \pmod{p}$
и умножение по двоен модул

: $F_1(x) F_2(x) \quad (\operatorname{modd} \ p,f(x))$ образува поле на Галоа $\mathbf{GF}(p^m)$ .
Доказателство. ∇ Всички елементи от множеството $\mathbb P_{p,f}$ са различни , понеже всеки се определя от набора на своите коефициенти $(A_0,A_1,\dots,A_{m-1})$ еднозначно. Всеки от коефициентите, независимо от другите, може да приeма p различни стойности, следователно $\operatorname{Card} ( \mathbb P_{p,f} ) = p^m$ .
Въедените в множеството $\mathbb P_{p,f}$ операции удовлетворяват аксиомите на поле; сложност има само при проверката на аксиомата за существуване на многочлен, обратен на произволен многочлен $F(x) \in \mathbb P_{p,f}, F(x) \not\equiv 0$ относно умножаването по двоен модул

.
Трябва да се уверим , че существува многочлен $U(x) \in \mathbb P_{p,f}$ такъв, че $U(x)F(x) \quad (\operatorname{modd} \ p,f(x)) \equiv 1 \ .$
Да се възползваме от разсъжденията от ПОЛЕ ОТ ПОЛИНОМИ.
По предположенията на теоремата, многочленът

се явява неприводим по модул p, следователно, той е неприводим в множеството $\mathbb Z_{}$ .
Тогава всеки многочлен $F(x)\in \mathbb Z[x], F(x)\not\equiv 0$ от степен $\le m-1$ ще бъде взаимно прост с $f_{}(x)$ : $\operatorname{HOD}(f,F)\equiv 1$ .
Тогава съществуват многочлени $\tilde U(x)$ и $\tilde V(x)$ , изпълняващи тождеството на Безу $\tilde U(x) F(x)+ \tilde V(x) f(x) \equiv 1 \ ;192$ при това указаните многочлени еднозначно се определят при дополнителни ограничения за степента: $\deg \tilde U < \deg f = m \ .193$
Коефициентите на многочлените $\tilde U(x) 190$ и $\tilde V(x)191$ , в общия случай, са рационални.
Да умножим тъждеството на Безу с цяло число, за да го превърнем в целочислено.
Ще получим $\widehat U(x) F(x)+ \widehat V(x) f(x) \equiv \mathcal R \ ,$ където $\mathcal R$ — е някъкво цяло число, а $\widehat U(x)=\mathcal R \tilde U(x),\ \widehat V(x)=\mathcal R \tilde V(x)$ . § Ако се възползваме от разсъжденията от резултантата, то в качеството на $\mathcal R$ можем да използваме резултантата на многочлените

и $f_{}(x)$ , тогава многочлените $\widehat U(x)$ и $\widehat V(x)$ се построят по предложения в указания пункт алгоритм.
Да запишем последното тождество във вида $\widehat U(x) F(x) \equiv \mathcal R - \widehat V(x) f(x) \ ,$ Така получаваме, като следствие: $\widehat U(x) F(x) \equiv \mathcal R \pmod{f(x)} \ .$
Ако $\mathcal R=1$ , то ще получим търсения многочлен $U(x)= \widehat U(x) \pmod{p}$ .
Ако $\mathcal R \ne 1$ , но $\mathcal R$ не се дели на p, то существува число, обратно на числото $\mathcal R$ относно умножаването по модул p.

Умножавайки двете части на последното сравнение, ще получим доказваното сравнение $U(x) F(x) \equiv 1 \quad (\operatorname{modd} \ p,f(x))$ .
Остана да разгледаме последня случай $\mathcal R \equiv 0 \pmod{p}$ . Ако всички коефициенти на многочлените $\widehat U(x)$ и
$\widehat V(x)$ се делят на p, то да разделим тождество на Безу на p.
Ако числото $\mathcal R/p$ не се дели на p, то към полученото тождество можем да приложим разсъжденията от предния абзац.
Ако числото $\mathcal R/p$ отново се дели на p, то ще се върнем в началото на този абзац и ще повторим разсъжденията.
Да предположим сега, че поне един от коефициентите на многочлените $\widehat U(x)$ или $\widehat V(x)$ не се дели на p.
Ако всички коефициенти $\widehat U(x)$ се делят на p, то и всички коефициенти $\widehat V(x) \equiv (\mathcal R - \widehat U(x) F(x))/f(x)$ се делят на p, което противоречи на предположението.
Нека не всички коефициенти $\widehat U(x)$ се делят на p, тогава $f(x) \widehat V(x) \equiv - F(x) \widehat U(x) \pmod{p} \ .$
Степените и на двата многочлена в дясната част не надминават $m_{}-1$ . ⟩ § Строгото — от формална гледна точка — въвеждането на обекта $\mathbb P_{p,f}$ от предната теорема трябва да се извърши на основата на класовете остатъци по модул p: $\mathbb P_{p,f} = \{ F (x)=A_0+A_1x+\dots+A_{m-1}x^{m-1} \ \mid \ \{A_0,A_1,\dots,A_{m-1}\} \subset \{\overline 0, \overline 1,\dots, \overline{p-1} \} \} \ .$
Авторът е пренебрегнал строгостта заради нагледността.
От същите съображения, често ще използваме този обект във варианта $\mathbb P_{p,f} = \left\{ \begin{array}{c|l} F (x)=A_0+A_1x+\dots+A_{m-1}x^{m-1} & \{A_0,A_1,\dots,A_{m-1}\} \subset \\ & \subset \left\{-\frac{p-1}{2}, -\frac{p-1}{2}+1,\dots,-1, 0, 1, 2,\dots, \frac{p-1}{2} \right\} \end{array} \right\} \ ,$ за нечетни прости числа p.
Понякога това е по-удобно в сравнение с исползованата в теоремата версия, — поне поради това, че коефициентите на многочлените $F_{}(x)$ са по-малки по абсолютна стойност. П Пример. Ще построим поле $\mathbf{GF}(4)$ .
∇ Тук p = 2 и $m_{}=2$ . Полиномът

се явява неприводим по модул 2.
Согласно теоремата, множеството от четирите многочлена $\{0,1,x,x+1\}$ с операцията събиране по модул 2 и операцията умножение по двоен модул

образува поле.
Резултатите от операците, нанесени в таблиците $\begin{array}{c|cccc} \mathbb{+} & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1 \\ x+1 & x+1 & x & 1 & 0 \end{array} \qquad \qquad \begin{array}{c|cccc} \mathbb{\times} & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1 \\ x+1 & 0 & x+1 & 1 & x \end{array}$ и те напълно съответстват на приведените в началото на раздела, където се извеждат правилата на действията в произволно поле $\mathbf{GF}(4)$ .
С други думи, съществува изоморфизъм между произволно поле $\mathbf{GF}(4)$ ( например полето от четирите матрици,построено в края на → ПУНКТА ) и полето от многочлени, построено в този пример. ⟩ Т Теорема. Крайните полета от един и същи ред са изоморфни, т.е. между елементите на тези полета може да се установи такова взаимно-еднозначно съответствие, кето съхранява резултатите от събирането и умножението на елементите.
Доказателството на тази теорема, са приведени в литературата но се оказаха трудни за моите способности за разбиране и затова просто ще приведа пример. → ТУК.

Неприводими многочлени по модул

! В този пункт под неприводим многочлен се разбира нормализиран неприводим многочлен.

Теорема 1.
Всеки неприводим по модул p многочлен от степен n се явява делител на многочлена $x^{p^n}- x$ по модул p.
Доказателство.
∇ В предишния пункт беше доказано, что ако $f_{}(x)$ е неприводим по модул p многочлен от степен n то множеството $\mathbb P_{p,f}$ от многочлени от степен

с коефициенти от $\{0,1,\dots,p-1\}$ образува поле на Галоа $\mathbf{GF} (p^n)$ относно въведените операции събиране по модул p и умножаване по двойнен модул

.
Но тогава всеки многочлен $F(x) \in \mathbb P_{p,f}$ трябва да удовлетворява обобщената теорема на Ферма: $\left[F(x)\right]^{p^n} - F(x) \equiv 0 \quad (\operatorname{modd} \ p,f(x)) \ .$ В частност, това трябва да е вярно и за $F(x) \equiv x$ .
Тогава многочленът $x^{p^n}-x$ трябва да се дели на многочлена $f_{} (x)$ по модул p. ⟩ § Полученото в хода на доказателството твърдение за това, че всеки многочлен $F(x) \in \mathbb P_{p,f}$ трябва да притежава свойството $\left[F(x)\right]^{p^n} - F(x) \equiv 0 \quad (\operatorname{modd} \ p,f(x))$ ни се иска да проверим по косвен начин
Ще покажем, че то е пряко следствие от сравнението $x^{p^n} - x \equiv 0 \quad (\operatorname{modd} \ p,f(x))$ → ТУК.
По такъв начин, за да намерим всички неприводими по модул p многочлени от степен n трябва да разложим многочлена $x^{p^n}- x$ на неприводими по модул p множители.
При това част от множителите могат да имат степен $< n_{}$ .
Обаче, съществуването за произволни p и n неприводими по модул p многочлени от степен n изисква доказателство. Т Теорема 2. Ако елементът $\mathfrak a \in \mathbf{GF} (p^m)$ удовлетворява неприводимо уравнение от степен n, то равенството $\mathfrak a^{p^m} - \mathfrak a = \mathfrak e$ е възможно тогава и само тогдава, когато $m_{}$ се дели на n.
Доказателство → ТУК. Т Теорема 3. Многочленът $x^{p^m}- x$ се разлага по модул p на неприводими многочлени, степените на които са равни или $m_{}$ или са делители на $m_{}$ .
Пряко следствие от теорема 2 се явява Т Теорема 4. Да означим с $\xi_p (k)$ броят на неприводимите по модул p многочлени от степен $k_{}$ .
Вярно е равенството $p^m=\sum_{k} k \xi_p (k) \ ;$ като сумирането се извършва по всички индекси $k_{}$ , делители на числото $m_{}$ . ? Да се определи $\xi_p (m)$ в случай на просто $m_{}$ .
Да се установи в този случай асимптотиката $\xi_p (m)/p^m$ при $m \to \infty$ . => Ако в каноническото разлагане на числото $m_{}$ на множители се съдържат само различни прости числа, то в сила е равенството: $\xi_p (m) =\frac{1}{m} \left(p^m- \sum_{k_1} p^{m/k_{_1}}+\sum_{k_{_1},k_{_2}} p^{m/(k_{_1}k_{_2})}- \sum_{k_{_1},k_{_2},k_{_3}} p^{m/(k_{_1}k_{_2}k_{_3})} + \dots \right) \ ,$ където $k_1,k_2,k_3,\dots$ пробягва всевъзможните делители на числото $m_{}$ . П Пример. Да се определи $\xi_p (30)$ .
∇ Понеже $30=2\cdot 3 \cdot 5$ , имаме: $\xi_p (30) = \frac{1}{30} \left(p^{30}-p^{15}-p^{10}-p^6+p^5+p^3+p^2-p \right) \ .$
Понеже, $\xi_2 (30)= 35790267,\ \xi_3 (30) =6863037256208$ . ⟩
В полето на Галоа первообразен корен от степен n от единицата се нарича елемент $\mathfrak a$ , удовлетворяващ условията $\mathfrak a^n=\mathfrak e \ , \mathfrak a^k \ne \mathfrak e \quad npu \quad k\in \{1,2,\dots,n-1\} \ .$ Ще казваме също, че $\mathfrak a$ принадлежи на показателя n или, че $\mathfrak a$ имеет порядок n. § Последният вариант соответства на определенето на порядък на елемент група, каквато (относно операцията умножение) се явява полето на Галоа. Т Теорема. В полето на Галоа $\mathbf{GF} (p^m)$ существуват първообразни корени от степен

от единицата.
Доказателство (и критерий, често позволява бързо да се намерят такива корени ) → ТУК.
В полето $\mathbf{GF} (p^m)$ първообразният корен от степен

от единицата се нарича примитивен елемент на полето. => Броят на примитивните елементи на полето $\mathbf{GF} (p^m)$ е равен на $\phi(p^m-1)$ , където $\phi$ — е функцията на Ойлер. => Във всяко поле групата на Галоа - групата относно умножението е циклична, с други думи : всички ненулеви елементи на полето $\mathbf{GF} (p^m)$ се намират в множеството $\{ \mathfrak A^0,\mathfrak A^1,\dots,\mathfrak A^{p^m-1} \}$ където $\mathfrak A$ е произволен примитивен елемент. П Пример 1. Нека

. Избирайки в качеството на неприводим по модул $3_{}$ многочлен

, ще получим, че елементите на полето $\mathbf{GF} (3^2)$ трябва да бъдат многочлени от степен не по-голяма от 1 с коефициенти от множеството $\{-1,0,1\}$ .
Да вземем в качеството на примитивен елемент на полето многочлена, тъждествено равен на $x_{}$ .
Последователно повдигайки го в степен ще получим: $x^0\equiv 1,\ x^1\equiv x,\ x^2 \equiv x+1 \quad (\operatorname{modd} \ 3,x^2-x-1 ) , \ x^3\equiv x\cdot x^2 \equiv x^2+x\equiv 2\,x+1 \equiv - x+1 ,$ т.е. всеки път умножаваме резултата от предната стъпка на $x_{}$ и в дясната част извършваме формална смяна $x^2 \to x+1$ ; $\begin{array}{l} x^4\equiv -x^2+x \equiv -x-1+x\equiv -1,\\ x^5 \equiv -x,\\ x^6 \equiv -x^2 \equiv -x-1,\\ x^7 \equiv -x^2-x\equiv -x-1-x \equiv x-1, \\ x^8 \equiv x^2-x \equiv 1 \ . \end{array}$ Циклът е завършен. ⟩ Т Теорема 6. Полиномът $x^{p^m}- x$ съдържа неприводими по модул p множители от степен $m_{}$ .
Доказателство.
∇ Ако первообразният корен $\mathfrak a$ от степен

от единицата би удовлетворявал уравнене от степен

то от теорема 1, той би удовлетворявал също и уравнението $\mathfrak a^{p^n} - \mathfrak e = \mathfrak o$ , което предвид неравенството

е невъзможно. ⟩ П Пример 2. Разложете многочлена $x^{16}-x$ на неприводими по модул 2 множители.
∇ Ще се возползваме от резултата от пункта УРАВНЕНИЕ НА ДЕЛЕНИЕТО НА КРЪГА. $x^{16}-x \equiv x \left(x^{15}-1 \right) \equiv x\, X_1(x)X_3(x)X_5(x)X_{15}(x) \equiv$ $\equiv x(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^8-x^7+x^5-x^4+x^3-x+1) \ .$ Тук многочлените

— са непривдими в $\mathbb Z_{}$ .
За да намерим разлагане на неприводими по модул 2 многочлени, ще се восползваме в началото от резултата на теорема 3 за определяне на броя на тези неприводими многочлени.
Имаме: $\begin{array}{rcrrr} 16 & = & 4 \xi (4) & + 2\xi (2) & + \xi (1), \\ 4 & = & & 2\xi (2) & + \xi (1), \\ 2 & = & & & \xi (1), \end{array}$ откъдето: $\xi (1)=2, \xi (2)=1, \xi (4)=3$ .
По такъв начин, получаваме че по модул 2 има ( точно ) 2 неприводими линейни многочлени, които вече се срещат в разлагането:
$x \quad$ и $\quad x-1 \equiv x+1 \pmod{2} \ ;$
Неприводимият многочлен от 2-а степен е единствен — и той също вече се съдержа в разлагането: $x^2+x+1 \ .$
Що се отнася до неприводимите многочлени $4_{}$ -а степен, то те трябва да бъдат точно $3_{}$ на брой.
Единият от тях вече се съдържа в разлагането: $x^4+x^3+x^2+x+1 \ ;$ а двата осталнали се съдържат в разлагането на

на множители по модул 2: $x^8-x^7+x^5-x^4+x^3-x+1 \equiv (x^4+x^3+1)(x^4+x+1) \pmod{2} \ .$ ⟩ П Пример 3. Намерете всички неприводими по модул 2 многочлени $3_{}$ -??та степен. ∇ За получаването на тези многочлени — в съответствие с теорема 3 — трябва да разложим на множители многочлена $x^{2^3}-x$ . Имаме $x^{8}-x\equiv x(x-1)(x^6+x^5+x^4+x^3+x^2+x+1) \equiv x(x-1)(x^3+x^2+1)(x^3+x+1) \pmod 2 \ .$ Двата получени многочлена $3_{}$ -??та степен са неприводими по модул 2, понеже от теорема 3 получаваме $\begin{array}{rcrr} 4 & = & 3\xi (3) & + \xi (1), \\ 2 & = & & \xi (1), \end{array}$ откъдето $\xi (3)=2$ . ⟩ П Пример 4. Разложете многочлена $x^{9}-x$ на неприводими по модул $3_{}$ множители.
∇ Тук

и от теоремата имаме $\begin{array}{rcrr} 9 & = & 2\xi (2) & + \xi (1), \\ 3 & = & & \xi (1), \end{array}$ т.е. $\xi (1)=3, \xi (2)=3$ .
Да разложим многочлена $x^{9}-x$ на неприводими множители над $\mathbb Z_{}$ : $x^{9}-x \equiv x(x-1)(x+1)(x^2+1)(x^4+1) \ .$
Тук многочленът

трябва да е неприводим по модул $3_{}$ .
Полиномът

трябва да се разлага по модул $3_{}$ на два множителя 2 - а степен.
Ще търсим един от тези множителели по метода на неопределените коефициенти.
Ако приемем че той е равен на

, то резултатът от делението с многочлена

ще е $x^4+1 \equiv (x^2+ax+b)(x^2-ax+a^2-b)+a(2b-a^2)x+(b^2-a^2b+1) \ .$
Коефициентите на остатъка ще приравним на нула по модул $3_{}$ : $a(2b-a^2)\equiv_{_{3}} 0 ,\ b^2-a^2b+1 \equiv_{_{3}} 0 \ .$
Ако от първото сравнение вземем $a \equiv_{_{3}} 0$ , то от второто сравнение ще получим $b^2+1 \equiv_{_{3}} 0$ .
Това сравнение няма решения. Следователно, от първото сравнение трябва да изберем друга възможност: $a^2 \equiv_{_{3}} 2 b \quad \iff \quad a^2 \equiv_{_{3}} -b ;$ заместваме го във второто сравнение: $2b^2+1 \equiv_{_{3}} 0 \quad \iff \quad - b^2+1 \equiv_{_{3}} 0 \quad \iff \quad b \equiv_{_{3}} \pm 1 \ .$ Ако $b \equiv_{_{3}} 1$ , то $a^2 \equiv_{_{3}} - 1$ или $a^2 \equiv_{_{3}} 1$ .
Първото сравнение е невъзможно.
Неприводимите по модул $3_{}$ многочлени 2-а степени са

. ⟩

Полиноми над GF(2)

Най-важни за приложенията в теорията на кодирането са полиномите от полето $\mathbf{GF}(2^m)$ .
Да разгледаме примери на полета от многочлени с коефициенти от множеството {0, 1} —
тези многочлени се наричат многочлени над GF(2).
Чрез примери ще демонстрираме още един път резултатите от предните пунктове.
Да забележем, че всеки ( не тождествено нулев ) многочлен от това поле е винаги нормализиран. ? Докажете, че всеки неприводим по модул 2 многочлен от степен

има нечетен брой едночлени. П Пример. Да изследваме полето $\mathbf{GF}(16)$ .
∇ Полето съдържа 16 елемента - многочлени от вида

при $\{A_0,A_1\} \in \{1,2\}$ .
Сега трябва да определим операцията умножение. Разлагането на многочлена $x^{16}-x$ на неприводими по модул 2 множители бе показано в предишния пункт: $x^{16}-x \equiv_{_{2}} x(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^4+x^3+1)(x^4+x+1) \ .$
При всеки избор на неприводим многочлен $f_{}(x)$ от степен $4_{}$ от трите, участващи в това разлагане, операцията за умножение по двоен модул

ще удовлетворява аксиомите на поле. Да проверим това за избора $f_{}(x)=x^4+x+1$ .
Следващата таблица изразява всички многочлен от полето чрез изразите за степени $\{x^{k} \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14} 304$ : таблица 305

(и ако бихме продължили тази таблица, то на следващата стъпка бихме попаднали на цикъл: $x^{15} \quad (\operatorname{modd} \ 2,f(x)) \equiv 1$ ).
В третия стълб стоят двоичните набори на коефициентите на многочлените, разглеждани в разлагането по намаляващи степени $x_{}$ .
В четвъртия стълб са отбелязани примитивните елементи на полето, т.е. елементите, чиито степени порождат всички ненулеви елементи на полето (единият от тях е многочлен, който е тъждествено равен $x_{}$ , по който, всъщност, и е съставена таблицата; със същия успех бихме могли и да разглеждаме и $\{\left(x^2\right)^k \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14}$ или $\{\left(x^{11}\right)^k \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14}$ , и т.н.).
Броят на примитивните елементи е равен на $\phi(2^4-1)=\phi(15)=8$ .
Всички те трябва да удовлетворяват алгебричните уравнения, чиито степени са равни на делителите на числото 16
Всички тези уравнения могат да се получат от разлагането на многочлена $x^{16} - x$ на неприводими по модул 2 множители. Да проверим това. За да избегнем усложненията , ще разглеждаме неприводимите многочлени спрямо променливата $\mathfrak x$ .
Да проверим, че многочлените

удовлетворяват уравнението $\mathfrak x^4+\mathfrak x+\mathfrak e= \mathfrak o$ ;
Навсякъде по-долу сравненията се изчисляват по двоен модул

: $x^4+x+1 \equiv 0,\ (x^2)^4+(x^2)+1 \equiv x^8+x^2+1 \equiv x^2+1+x^2+1 \equiv 0,$ $\begin{matrix} (x^4)^4+(x^4)+1 & \equiv &(x+1)^4+(x+1)+1 \equiv x+(x+1)+1 \equiv 0 , \\ (x^8)^4+(x^8)+1 & \equiv & (x^{2}+1)^4+(x^2+1)+1 \equiv x^2+(x^2+1)+1 \equiv 0 \ . \end{matrix}$
Оставащите $4_{}$ примитивни елементи на полето, имено, $x^7,x^{11},x^{13},x^{14}$ трябва да удовлетворяват друго уравнение от $4_{}$ -та степен, което сответства на един от оставащите неприводими многочлени от същата степен.
В същност, те удовлетворяват уравнението $\mathfrak x^4+\mathfrak x^3+\mathfrak e= \mathfrak o$ : $(x^7)^4 + (x^7)^3+1 \equiv x^{28}+x^{21}+1 \equiv x^{13}+x^{6}+1\equiv x^3+x^2+1+(x^3+x^2)+1 \equiv 0 \ .$
Последните изчисления извършваме отчитайки че $x^{15} \equiv 1$ и чрез исползане на построената по-горе таблица за степените $x^{k}$ .
Примитивните елементи на полето, т.е. елементите от ред $15_{}$ , са исчерпани.
Всички останали елементи на полето имат редове, равни на $1_{}, 3_{}$ или $5_{}$ , т.е. — в соответствие с теоремата от предния пункт — делители на числото $15_{}$ .
Да разгледаме редицата $\{\left(x^3\right)^k \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14}$ : $(x^3)^0 \equiv 1,\ (x^3)^1 \equiv x^3,\ (x^3)^2 \equiv x^6 \equiv x^3 +x^2,\ (x^3)^3 \equiv x^9 \equiv x^3 +x,\ (x^3)^4 \equiv x^{12} \equiv x^3 +x^2+x+1,\ (x^3)^5 \equiv x^{15} \equiv 1 \ .$
И така, елементът на полето $x^{3}$ принадлежи на показател $5_{}$ , на този показател принадлежат и неговите степени, т.е. многочлените $x^3 +x^2,\ x^3 +x,\ x^3 +x^2+x+1$ .
Всички тези многочлени удовлетворяват уравнението $\mathfrak x^4+\mathfrak x^3+\mathfrak x^2+\mathfrak x+\mathfrak e= \mathfrak o$ , съответстващо на третия неприводим многочлен от $4_{}$ -та степен в разлагането на $x^{16}-x$ . За всеки случай, да направим проверка с x⁹:

Сега да разгледаме оставащите елементи на полето:

и $x^{10}$ .
Те трябва да принадлежат на показателя $3_{}$ , което са проверява непосредствено.
Освен това, те трябва да удовлетворяват и неприводимо уравнение от разлагането на $x^{16}-x$ .
Изборът е еднозначен — единственият кандидат се явява уравнението от втора степен $\mathfrak x^2+ \mathfrak x + \mathfrak e = \mathfrak o$ : $(x^5)^2+x^5+1 \equiv x^2+x+1 + (x^2+x)+1 \equiv 0 \ .$ Накрая, неутралните елементи на полето $0_{}$ и 1 — с тях всичко е просто. ⟩
Извод. Полето на Галоа едновременно притежава свойствата на циклина група, линейно пространство и алгебрично уравнение с цели коефициенти. От една страна, всички ненулеви елементи на полето могат да бъдат представени като степени на един единствен. От друга страна, операцията събиране на многочлени е еквивалентна на събирането на вектори, с координати техните коефициенти. Да отбележим, че в линейнто пространства не се въвежда аналог на умножението на вектори — такова, че при умножението на два вектора да се получава отново вектор. От трета сторана, всички елементи на полето се разбиват на подмножества, всяко от които съответства на неприводимо алгебрично уравнение — казва се, че елементите на полето се явяват корени на неприводими полиноми над GF(2) многочлени. ? За предния пример да се съставят подобни таблици на степените $\{\mathfrak a^{k} \quad (\operatorname{modd} \ 2,f(x)) \}_{k=0}^{14}$ при избор на многочлена $f_{}(x)$
а)

; б)

; а също подходящ примитивен елемент $\mathfrak a$ .
∇ → ТУК. ⟩
Сега да се заемем с неприводимите многочлени. В началото да оценим техният брой — в абсолютно количество, а също по отношение към общото количество на многочлени от степен $k_{}$ :
∇ $\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} k & 1& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 12 & 21 & 25 & 30 \\ \hline \xi(k) & 2 & 1 & 2 & 3 & 6 & 9 & 18 & 30 & 56 & 99 & 335 & 99858 & 1342176 & 35790268 \\ \hline \xi(k)/2^k & 1 & 0.25 & 0.25 & 0.19 & 0.19 & 0.14 & 0.14 & 0.12 & 0.11 & 0.10 & 0.08 & 0.05 & 0.04 & 0.03 \end{array}$
⟩ ? Да разложим многочлена $x^{64}-x$ на неприводими по модул 2 множители.
∇Решението → ТУК.⟩

Многочлени над GF(p)

Сега да обобщим резултата от разгледаните в предишния пункт примери. Ще разглеждаме многочлените $F_{}(x)$ над $\mathbf{GF}(p)$ . Нас ни интересуват решенията на уравнението $F(\mathfrak x) \equiv \mathfrak o \ .$ сред елементите на крайното поле $\mathbf{GF}(p^m)$ .
Всяко такова решение $\mathfrak a$ ще наричаме корен на многочлена $F_{}$ в полето $\mathbf{GF}(p^m)$ . Т
Теорема 1. Нека $F_{}(x)$ е неприводим по модул p многочлен от степен n и $\mathfrak a \in \mathbf{GF}(p^m)$ е негов корен. Тогава множеството от корени $F_{}(x)$ в полето $\mathbf{GF}(p^m) 106$ съвпада с $\mathfrak a, \mathfrak a^p, \mathfrak a^{p^2},\dots, \mathfrak a^{p^{n-1}} \ . 341$
Доказателство. ∇Ще използваме теоремата на Шьонеман: За произволен многочлен $F(x)\in \mathbb Z[x]$ се изпълнява сравнението $\left[F(x)\right]^p \equiv F(x^p) \pmod{p} \ .$ Тогава ако $F(\mathfrak a)= \mathfrak o$ , то и $F(\mathfrak a^p)= \mathfrak o$ , но тогава и $F((\mathfrak a^p)^p)= \mathfrak o$ , и т.д.
От друга страна, всички елементи от множеството $\{ \mathfrak a^{p^j} \}_{j=0}^{n-1}$ са различни. Наистина, ако се изпълнява равенството $\mathfrak a^{p^j}=\mathfrak a^{p^k} \qquad npu \qquad 0\le j< k \le n-1 \ ,$ то повдигайки на степен $p^{n-k}$ , ще получим равенството $\mathfrak a^{p^{n+j-k}}=\mathfrak a^{p^n} = \mathfrak a \ . 349$ Последното равенство следва от доказателството на теоремата от → този ПУНКТ. Но равенството $\mathfrak a^{p^{n+j-k}}= \mathfrak a$ е невъзможно, понеже

, а предвид теоремата 3 от → ПУНКТА, многочленът $x^{p^{n+j-k}}-x$ се дели на тези неприводими по модул p многочлени, чиито степени са делители на

и, следователно, не могат да се делят на $F_{}(x)$ . ⟩ Т Теорема 2. Всички корени на неприводимия многочлен $F_{}(x)$ принадлежат на един показател ( имат еднакъв ред ). Показателят на корените на неприводимия многочлен се нарича показател, на който този многочлен принадлежи. Ако неприводимият многочлен $F_{}(x)$ принадлежи на показателя $\ell_{}$ , то той е делител на многочлена $x^{\ell}-1$ , но той не е делител нито на един от многочлените

при $k\in \{1,\dots,\ell-1 \} 357$ .
Неприводимият многочлен от степен $m_{}$ над $\mathbf{GF}(p)$ се нарича примитивен, ако негов корeн е примитивен елемент на полето $\mathbf{GF}(p^m)$ . В този случай, този корен принадлежи на показателя

, и по теорема 2, всички корени $F_{}(x)$ принадлежат на същия показател, т.е. се явяват примитивни елементи на полето. => Броят на неприводимите многочлени от степен $m_{}>1$ е равен на $\phi (p^m-1)/m$ . § Получава се, че броят $\phi (p^m-1)$ трябва да принадлежи изцяло на $m_{}$ . Резултат, който изобщо не е очевиден от елементарни съображения. Всъщност, той е верен даже в случая когато вместо p се разглежда съставно число; виж следствието от теорема 3 → ТУК. => Неприводимият многочлен $F_{}(x)$ от степен $m_{}$ е примитивен тогава и само тогава, когато той не е делител нито на един от многочлените

при $k\in \{1,\dots,p^m-2 \}$ .
Ако каноничното разлагане на числото

има вида: $p^m-1=p_1^{{\mathfrak m}_{_1}}p_2^{{\mathfrak m}_{_2}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{_{\mathfrak r}}} \ ,$ то за да бъде неприводимия многочлен $F_{}(x) 135$ от степен $m_{} 055$ примитивен, е необходимо и достаточно, той да не е делител на нито един от многочлените $x^{(p^m-1)/p_j}-1$ при $\forall j \in \{1,\dots, \mathfrak r \}363$ . П Пример. От трите неприводими многочлени $4_{}$ -а от степен: $x^4+x+1, \ x^4+x^3+1, \ x^4+x^3+x^2+x+1$ примитивни ще бъдат само первия и втория. За подробен анализ виж → ТУК. П Пример. Примитивни многочлени $6_{}$ -а от степен виж → ТУК.
Превод от руски - Станчо Вълканов Павлов