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


Вспомогательная страница к пункту ☞ ПОЛИНОМЫ, НЕПРИВОДИМЫЕ ПО МОДУЛЮ. Содержание очень близко по смыслу к понятию первообразный корень из раздела ☞ ИНДЕКС (ДИСКРЕТНЫЙ ЛОГАРИФМ) .


Примитивные элементы поля

В поле Галуа первообразным корнем степени 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 ( обобщенная теорема Ферма ). Тогда

\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_{}.

Итак, при любом k<n таком, что \operatorname{HOD} (k,n)=1, элементы \mathfrak a^k принадлежат показателю n_{}, если \mathfrak a принадлежит этому показателю. С другой стороны, множество

\{ \mathfrak a^k \ \mid \ k\in \{1,\dots,n-1\}, \ \operatorname{HOD} (k,n)=1 \}

содержит все элементы, принадлежащие показателю n_{}, поскольку множество

\{ \mathfrak a^k \ \mid \ k\in \{0,\dots,n-1\} \}

содержит все решения уравнения \mathfrak x^n= \mathfrak e; а при условии \operatorname{HOD} (k,n)>1 элемент \mathfrak a^k принадлежит показателю меньшему, чем n_{} (см. аналогию с первообразными корнями из единицы в поле комплексных чисел ). Число элементов в первом из этих множеств известно — оно равно значению функции Эйлера от числа 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 \ ;

с другой же стороны, для функции Эйлера справедливо аналогичное равенство

\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_{} из раздела ☞ ИНДЕКС (дискретный логарифм).

Т

Теорема 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}}} \ ,

то для того чтобы элемент \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 из пункта ☞ ПЕРВООБРАЗНЫЙ КОРЕНЬ.

П

Пример. Будет ли полином 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?


Источник. Материалы этого пункта взяты (с незначительными модификациями) из

Чеботарев Н. Основы теории Галуа. Часть I. М.-Л.ОНТИ.1934

2013/05/07 09:30 редактировал au