!!§!! Вспомогательная страница к пункту ☞ ((:gruppe:galois#полиномы_неприводимые_по_модулю ПОЛИНОМЫ, НЕПРИВОДИМЫЕ ПО МОДУЛЮ)). Содержание очень близко по смыслу к понятию //первообразный корень// из раздела ☞ ((:modular:index ИНДЕКС (ДИСКРЕТНЫЙ ЛОГАРИФМ) )). ---- ==Примитивные элементы поля== В поле Галуа **первообразным корнем степени 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**. !!Т!! **Теорема 1.** //В поле Галуа// $ \mathbf{GF} (p^m) $ //существуют первообразные корни степени// $ p^m-1 $ //из единицы.// В поле $ \mathbf{GF} (p^m) $ первообразный корень степени $ p^m-1 $ из единицы называется **примитивным элементом поля**. **Лемма 1.** //Пусть// $ \mathfrak a \in \mathbf{GF} (p^m), \mathfrak a \ne \mathfrak o $ --- //первообразный корень степени// $ n_{} $ //из единицы. Тогда// $ p^m-1 $ //делится на// $ n_{} $. **Доказательство.** Если $ p^m-1 $ не делится на $ n_{} $, т.е. $$ p^m-1 = nq+ r \quad npu \quad \{r,q\} \subset \mathbb N \quad u \ 0< r< n \ , $$ то одновременно выполняется и $ \mathfrak a^n=\mathfrak e $ и $ \mathfrak a^{p^m-1}=\mathfrak e $ ( ((:gruppe:galois#обобщенная_теорема_ферма обобщенная теорема Ферма)) ). Тогда $$ \mathfrak a^r=\mathfrak a^{(p^m-1)-nq}=\mathfrak a^{p^m-1} \cdot \left( \mathfrak a^{nq} \right)^{-1} = \mathfrak e \cdot \mathfrak e = \mathfrak e \ , $$ т.е. $ \mathfrak a $ является корнем из единицы степени меньшей $ n_{} $. ♦ Обозначим $ \psi (n) $ --- число элементов поля $ \mathbf{GF} (p^m) $, принадлежащих показателю $ n_{} $. Согласно лемме 1, число $ n_{} $ должно быть делителем числа $ p^m-1 $. Кроме того, если $ \{1,d_1,d_2,\dots, p^m-1\} $ --- множество всех делителей числа $ p^m-1 $, то $$ \psi (1)+\psi(d_1)+\psi(d_2)+\dots+\psi(p^m-1) = p^m-1 \ , $$ поскольку любой элемент поля принадлежит одному и только одному показателю. **Лемма 2.** //Если// $ \mathfrak a $ //принадлежит показателю// $ n_{} $ //и число// $ k_{} $ //взаимно просто с// $ n_{} $, //то и// $ \mathfrak a^k $ //принадлежит показателю// $ n_{} $. **Доказательство.** В самом деле, $ \left( \mathfrak a^{k} \right)^n = \left( \mathfrak a^{n} \right)^k = \mathfrak e $. С другой стороны, при $ n_1 < n $ равенство $ \left( \mathfrak a^{k} \right)^{n_1} = \mathfrak e $ невозможно. В самом деле, если оно все же выполнено при $ k_{} $ взаимно простом с $ n_{} $. Тогда, существуют целые числа $ u_{} $ и $ v_{} $, обеспечивающие выполнение равенства $ u\,k+v\, n =1 $. Возведем равенство $ \left( \mathfrak a^{k} \right)^{n_1} = \mathfrak a^{kn_1} = \mathfrak e $ в степень $ u_{} $: $$ \mathfrak e = \mathfrak a^{kun_1} = \mathfrak a^{n_1} \mathfrak a^{n_1(ku-1)} = \mathfrak a^{n_1} \mathfrak a^{-vnn_1} = \mathfrak a^{n_1} \ , $$ т.е. $ \mathfrak a $ является корнем из единицы степени меньшей $ n_{} $. ♦ Итак, при любом $ k1 $ элемент $ \mathfrak a^k $ принадлежит показателю меньшему, чем $ n_{} $ (см. аналогию с первообразными корнями из единицы ((:complex_num#корни_из_единицы в поле комплексных чисел)) ). Число элементов в первом из этих множеств известно --- оно равно значению ((:numtheory#функция_эйлера функции Эйлера)) от числа $ n_{} $, т.е. $ \phi (n) $. Таким образом, для любого числа $ n \in \mathbb N $ будет либо $ \psi(n)=0 $, либо $ \psi(n) = \phi (n) $, т.е., в общем случае, $$ \psi(n) \le \phi(n) \ . $$ **Лемма 3.** //Если// $ p^m-1 $ //делится на// $ n_{} $, //то// $ \psi (n) = \phi (n) $. **Доказательство.** Если $ \{1,d_1,d_2,\dots, p^m-1\} $ --- множество всех делителей числа $ p^m-1 $, то, с одной стороны, имеем выведенное выше равенство: $$ \psi (1)+\psi(d_1)+\psi(d_2)+\dots+\psi(p^m-1) = p^m-1 \ ; $$ с другой же стороны, для функции Эйлера ((:complex_num:circlediv справедливо аналогичное равенство)) $$ \phi (1)+\phi(d_1)+\phi(d_2)+\dots+\phi(p^m-1) = p^m-1 \ . $$ Вычитаем из второго первое: $$ \sum_{d} \left[ \phi (d) - \psi (d) \right] =0 \ , $$ где суммирование идет по всем числам $ d_{} $, являющимися делителями числа $ p^m-1 $. Каждое слагаемое --- по неравенству, выведенному выше, --- неотрицательно. Следовательно, оно должно равняться нулю. ♦ **Доказательство** теоремы 1 следует из леммы 3 при $ n=p^m-1 $. Фактически мы получили и точное значение для количества первообразных корней степени $ p^m-1 $ из единицы, т.е. для количества примитивных элементов поля $ \mathbf{GF} (p^m) $ --- оно равно $$ \phi (p^m-1) \ . $$ ♦ Как найти примитивный элемент поля? Воспользуемся аналогией этого объекта с первообразным корнем по модулю простого числа $ p_{} $ из раздела ☞ ((:modular:index#первообразный_корень ИНДЕКС (дискретный логарифм))). !!Т!! **Теорема 2.** //Если ((:numtheory#каноническое_разложение_числа каноническое разложение)) числа// $ 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}}} \ , $$ //то для того чтобы элемент// $ \mathfrak A \in \mathbf{GF} (p^m) $, //был примитивным элементом этого поля, необходимо и достаточно, чтобы// $$ \mathfrak A^{(p^m-1)/p_j} \not\equiv \mathfrak e \quad npu \quad \forall j\in \{1,\dots, \mathfrak r\} \ . $$ **Доказательство** аналогично доказательству теоремы 5 из пункта ☞ ((:modular:index#первообразный_корень ПЕРВООБРАЗНЫЙ КОРЕНЬ)). ♦ !!П!! **Пример.** Будет ли полином $ x^3+x^2 $ примитивным элементом поля $ \mathbf{GF}(16) $, если операция умножения в этом поле определена по двойному модулю $ 2, x^4+x^3+x^2+x+1 $? **Решение.** Имеем $ 2^4-1=15=3\cdot 5 $. $$ (x^3+x^2)^{15/3} \equiv_{2} x^{15}+x^{14}+x^{11}+x^{10} \equiv x^3+x^2+1 \not\equiv 1 \quad (\operatorname{modd} \ 2,x^4+x^3+x^2+x+1) ; $$ $$ (x^3+x^2)^{15/5} \equiv_{2} x^9+x^8+x^7+x^6 \equiv 1 \quad (\operatorname{modd} \ 2,x^4+x^3+x^2+x+1) . $$ **Ответ.** Нет. Лемма 2 позволяет найти все семейство примитивных элементов поля, если один уже обнаружен. !!Т!! **Теорема 3.** //Если// $ \mathfrak A \in \mathbf{GF} (p^m) $ --- //примитивный элемент поля, то// $ \mathfrak A^k $// будет примитивным элементом поля тогда и только тогда, когда показатель// $ k_{} $ //взаимно прост с// $ p^m-1 $: $ \operatorname{HOD} (k,p^m-1)=1 $. !!П!! **Пример.** Определить все примитивные элементы поля $ \mathbf{GF}(16) $, если операция умножения в этом поле определена по двойному модулю $ 2, x^4+x^3+1 $. **Решение.** С помощью теоремы 2 устанавливаем, что полином $ x_{} $ является примитивным элементом поля. Но тогда, в соответствии с теоремой 3, полиномы $$ x^2,x^4,\ x^7\equiv x^2+x+1,\ x^8\equiv x^3+x^2+x,\ x^{11} \equiv x^3+x^2+1,\ x^{13}\equiv x^2+x,\ x^{14}\equiv x^3+x^2 \quad (\operatorname{modd} \ 2,x^4+x^3+1) $$ также должны быть также примитивными элементами поля. Их (вместе с $ x_{} $) как раз $ \phi(15)=8 $ штук, так что больше примитивных корней нет. ♦ !!?!! Будет ли полином $ x_{} $ примитивным элементом поля $ \mathbf{GF}(2^8) $, если операция умножения в этом поле определена по двойному модулю **a)** $ 2, x^8+x^4+x^3+x^2+1 $; **b)** $ 2, x^8+x^4+x^3+x+1 $? ==Источник== Материалы этого пункта взяты (с незначительными модификациями) из \\ [1]. **Чеботарев Н.** //Основы теории Галуа. Часть I.// М.-Л.ОНТИ.1934