Какво трябва да знаем?

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

Алексей Юрьевич Утешев
§
В този раздел буквата 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_{} е съставно: M=M_1M_2 при M_1<M и M_2<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} определя   p^2   различни   елементи на полето   \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} \ , което определя   p^3   различни   елемента от полето   \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 \ .
Доказателството е аналогично на доказателството малка теорема на Ферма.
Да означим за краткост q=p^m, и да разгледаме множеството от всички ненулеви елементи полето \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) \ ,
където F_1, F_2,G са многочлени с цели коефициенти и \deg F_1 < \deg F, \deg F_2< \deg F.
В противен случай ще казваме, че многочленът F_{}(x) е приводим по модул p или че F_{}(x) се дели на F_j(x) по модул p, или че F_j(x)   се явава делител 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 image145.jpg
П
Пример. Приводим ли е многочленът 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] се наричат сравними по двоен модул p, f(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_1(x)-F_2(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) на 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_1(x) на f_{}(x), в който допълнително се заместват коефициентите му с техните остатъци от делението на p.
П
Пример. За F_1(x)=5\,x^4-x^2+x-4, f(x)= x^3+2\,x^2+3\,x-6 и p=7 имаме:
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}
и умножение по двоен модул p, f(x): 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 относно умножаването по двоен модул p,f(x).
Трябва да се уверим , че существува многочлен U(x) \in \mathbb P_{p,f} такъв, че U(x)F(x) \quad (\operatorname{modd} \ p,f(x)) \equiv 1 \ .
Да се възползваме от разсъжденията от ПОЛЕ ОТ ПОЛИНОМИ.
По предположенията на теоремата, многочленът f(x) се явява неприводим по модул 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) и 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. Полиномът f(x)=x^2+x+1 се явява неприводим по модул 2.
Согласно теоремата, множеството от четирите многочлена \{0,1,x,x+1\} с операцията събиране по модул 2 и операцията умножение по двоен модул 2, x^2+x+1 образува поле.
Резултатите от операците, нанесени в таблиците
\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} от многочлени от степен < n с коефициенти от \{0,1,\dots,p-1\} образува поле на Галоа \mathbf{GF} (p^n) относно въведените операции събиране по модул p и умножаване по двойнен модул p,f(x).
Но тогава всеки многочлен 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) существуват първообразни корени от степен p^m-1 от единицата.
Доказателство (и критерий, често позволява бързо да се намерят такива корени ) ТУК.
В полето \mathbf{GF} (p^m) първообразният корен от степен p^m-1 от единицата се нарича   примитивен елемент на полето.
=>
Броят на примитивните елементи на полето \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. Нека   p=3, m=2. Избирайки в качеството на неприводим по модул 3_{} многочлен f(x)=x^2-x-1, ще получим, че елементите на полето \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 от степен   p^m -1 от единицата би удовлетворявал уравнене от степен n<m то от теорема 1, той би удовлетворявал също и уравнението \mathfrak a^{p^n} - \mathfrak e = \mathfrak o, което предвид неравенството p^n-1 < p^m-1 е невъзможно.
П
Пример 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) \ .
Тук многочлените X_j(x) — са непривдими в \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 \ ; а двата осталнали се съдържат в разлагането на x^8-x^7+x^5-x^4+x^3-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_{} множители.
Тук p=3,m=2 и от теоремата имаме
\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) \ .
Тук многочленът x^2+1 трябва да е неприводим по модул 3_{}.
Полиномът x^4+1 трябва да се разлага по модул 3_{} на два множителя   2 - а степен.
Ще търсим един от тези множителели по метода на неопределените коефициенти.
Ако приемем че той е равен на x^2+ax+b, то резултатът от делението с многочлена x^4+1 ще е 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-а степени са x^2+x-1 и x^2-x-1.

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

Най-важни за приложенията в теорията на кодирането са полиномите от полето   \mathbf{GF}(2^m).
Да разгледаме примери на полета от многочлени с коефициенти от множеството {0, 1}
тези многочлени се наричат многочлени над GF(2).
Чрез примери ще демонстрираме още един път резултатите от предните пунктове.
Да забележем, че всеки ( не тождествено нулев ) многочлен от това поле е винаги нормализиран.
?
Докажете, че всеки неприводим по модул 2 многочлен от степен   n> 1 има нечетен брой едночлени.
П
Пример.   Да изследваме полето   \mathbf{GF}(16).
Полето съдържа 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)(x^4+x^3+x^2+x+1)(x^4+x^3+1)(x^4+x+1) \ .
При всеки избор на неприводим многочлен f_{}(x) от степен   4_{} от трите, участващи в това разлагане, операцията за умножение по двоен модул 2,f(x)   ще удовлетворява аксиомите на поле. Да проверим това за избора 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.
Да проверим, че многочлените x, x^2,x^4,x^8 удовлетворяват уравнението   \mathfrak x^4+\mathfrak x+\mathfrak e= \mathfrak o;
Навсякъде по-долу сравненията се изчисляват по двоен модул 2,x^4+x+1:
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. За всеки случай, да направим проверка с x9:
Проверка
Сега да разгледаме оставащите елементи на полето: x^5 и 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)
а)   x^4+x^3+1;       б)   x^4+x^3+x^2+x+1; а също подходящ примитивен елемент \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 е невъзможно, понеже   n+j-k< n, а предвид теоремата 3 от →   ПУНКТА, многочленът x^{p^{n+j-k}}-x   се дели на тези неприводими по модул p многочлени, чиито степени са делители на n+j-k и, следователно, не могат да се делят на F_{}(x).
Т
Теорема 2. Всички корени на неприводимия многочлен   F_{}(x)   принадлежат на един показател ( имат еднакъв ред ). Показателят на корените на неприводимия многочлен се нарича показател, на който този многочлен принадлежи. Ако неприводимият многочлен F_{}(x) принадлежи на показателя \ell_{}, то той е делител на многочлена x^{\ell}-1, но той не е делител нито на един от многочлените x^k-1 при k\in \{1,\dots,\ell-1 \} 357.
Неприводимият многочлен от степен m_{}над \mathbf{GF}(p) се нарича примитивен, ако негов корeн е примитивен елемент на полето \mathbf{GF}(p^m). В този случай, този корен принадлежи на показателя p^m-1, и по теорема 2, всички корени F_{}(x) принадлежат на същия показател, т.е. се явяват примитивни елементи на полето.
=>
Броят на неприводимите многочлени от степен m_{}>1 е равен на \phi (p^m-1)/m.
§
Получава се, че броят \phi (p^m-1) трябва да принадлежи изцяло на   m_{}. Резултат, който изобщо не е очевиден от елементарни съображения. Всъщност, той е верен даже в случая когато вместо p се разглежда съставно число; виж следствието от теорема 3 →   ТУК.
=>
Неприводимият многочлен   F_{}(x) от степен   m_{} е примитивен тогава и само тогава, когато той не е делител нито на един от многочлените x^k-1 при k\in \{1,\dots,p^m-2 \}.
Ако каноничното разлагане на числото p^m-1 има вида: 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_{}-а от степен виж → ТУК.
Превод от руски - Станчо Вълканов Павлов