Многочлен над конечным полем

Многочленом $f(x)$ над конечным полем $\Bbb{F}_q$ называется формальная сумма вида

$f(x)=f_0+f_1 x+\ldots+f_m x^m,\quad f_i\in \Bbb{F}_q,\quad f_m\neq 0.$

Здесь $m$ — целое неотрицательное число, называемое степенью многочлена $f(x)$, а $x^k$ — элементы алгебры над $\Bbb{F}_q,$ умножение которых задаётся правилами:

$x^k \cdot x^m = x^{k+m},$

$x^0 \equiv 1.$

Такое определение позволяет умножать многочлены формально, не заботясь о том, что разные степени одного и того же элемента конечного поля могут совпадать.

Связанные определения

• Число $m\geqslant 0$ называется степенью полинома и обозначается как $\deg(f(x))$.
• Если $f_m=1$, то полином называется нормированным или унитарным. Полином всегда можно нормировать делением его на коэффициент $f_m$ при старшей степени.
• Сумма и произведение полиномов определены обычным образом, а операции с коэффициентами осуществляются в поле $\Bbb{F}_q$.
• Для двух полиномов $f(x)$ и $h(x)$ таких, что $\deg(f(x))\geqslant\deg(h(x))$, всегда найдутся полиномы $t(x)$ и $r(x)$ над полем $\Bbb{F}_q$, что будет выполняться соотношение

  $f(x)=t(x)h(x)+r(x).$

  • Если степень $r(x)$ строго меньше степени $h(x)$, то такое соотношение называется представлением полинома $f(x)$ в виде частного и остатка от деления $f(x)$ на $h(x)$, причем такое представление единственно. Ясно, что $f(x)-r(x)$ делится без остатка на $h(x)$, что записывается как $f(x)\equiv r(x)\pmod{h(x)}$.
  • Полином $h(x)$ называется делителем полинома $f(x)$, если $r(x)=0$.
• Полином является неприводимым над полем $\Bbb{F}_q$, если он не имеет нетривиальных делителей (степени большей 0 и меньшей $\deg(f(x))$).

Корни многочлена

Корнем называется всякий элемент поля, значение многочлена на котором равно нулю. Полином степени m имеет ровно m корней (с учётом кратности), принадлежащих некоторому расширенному полю $\Bbb{F}_Q,\quad \Bbb{F}_q\subseteq \Bbb{F}_Q$. Если $q=p^s$, где $p$ — простое, то $Q=p^S,\;S\geqslant s$. Исходя из свойств конечных полей, любой элемент поля $\Bbb{F}_Q$ является корнем двучлена $x^Q-x$. Таким образом, корни многочлена $f(x)$ также являются корнями двучлена $x^Q-x$.

Справедливы теорема Безу и следствия из неё:

Остаток от деления $f(x)$ на $(x-a)$ равен $f(a)$.

Если $x_0$ — корень $f(x)$, то $(x-x_0)$ делит $f(x)$.

Если $x_0,\;x_1,\;\ldots,\;x_m$ суть корни $f(x)$, то $f(x) = (x-x_0)(x-x_1)\ldots(x-x_m).$

Также справедлива следующая теорема:

Теорема 1. Если $x_0$ — корень $f(x)$, то $x_0^q$ — тоже корень $f(x)$.

Циклотомический класс

Следствием Теоремы 1 может быть тот факт, что, если $\alpha\in\Bbb{F}_Q$ — корень полинома $f(x)$ над полем $\Bbb{F}_q$, то и $\alpha^q,\;\alpha^{q^2},\;\alpha^{q^3},\;\ldots\in\Bbb{F}_Q$ являются его корнями.

Определение: циклотомическим классом над полем $\Bbb{F}_q,\;q=p^s$, порождённым некоторым элементом $\alpha\in\Bbb{F}_Q,\;Q=p^S$ называется множество всех различных элементов $\Bbb{F}_Q$, являющихся $q$-ыми степенями $\alpha$.

Если $\alpha$ — примитивный элемент (такой элемент, что $\alpha^{Q-1}=1$ и $\alpha^k\neq 1$ при $0<k<Q-1$) поля $\Bbb{F}_Q,\;Q=q^m$, то циклотомический класс $C=\{\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}\}$ над полем $\Bbb{F}_q$ будет иметь ровно $m$ элементов.

Следует отметить, что любой элемент из циклотомического класса может порождать этот и только этот класс, а, следовательно, и принадлежать только ему.

Примеры циклотомических классов

Пример 1. Пусть $q=2$, $Q=2^3=8$ и $\alpha$ — примитивный элемент поля $\Bbb{F}_8$, то есть $\alpha^7=1$ и $\alpha^i\neq 1$ при $i<7$. Учитывая также, что $\alpha^8=\alpha$, можно получить разложение всех ненулевых элементов поля $\Bbb{F}_8$ на три циклотомических класса над полем $\Bbb{F}_2$:

$\begin{matrix} \{1\}, \\ \{\alpha,\;\alpha^2,\;\alpha^4\}, \\ \{\alpha^3,\;\alpha^6,\;\alpha^5\}. \end{matrix}$

Пример 2. Аналогично можно построить классы на поле $\Bbb{F}_{16}$ над полем $\Bbb{F}_4$, то есть $q=4,\;Q=q^2=16$. Пусть $\alpha$ — примитивный элемент поля $\Bbb{F}_{16}$, значит $\alpha^{15}=1,\;\alpha^{16}=\alpha$.

$\begin{matrix} \{1\}, \\ \{\alpha,\;\alpha^4\},\;\{\alpha^2,\;\alpha^8\}, \\ \{\alpha^3,\;\alpha^{12}\},\;\{\alpha^5\},\;\{\alpha^{10}\}, \\ \{\alpha^6,\;\alpha^9\},\;\{\alpha^7,\;\alpha^{13}\}, \\ \{\alpha^{11},\;\alpha^{14}\}. \end{matrix}$

Связь с корнями полиномов

Следующая Теорема устанавливает связь между циклотомическими классами и разложением полинома $x^{Q-1}-1$ на неприводимые полиномы над полем $\Bbb{F}_q$.

Теорема 2. Пусть $\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}$ циклотомический класс, порожденный элементом $\alpha\in \Bbb{F}_{q^l}$ и полином $f(x)=f_0+f_1 x+f_2 x^2+\ldots+f_{m-1}x^{m-1}+x^m$ имеет в качестве своих корней элементы этого циклотомического класса, то есть $f(x)=(x-\alpha)(x-\alpha^q)\ldots(x-\alpha^{q^{m-1}}).$ Тогда коэффициенты $f_0,\;f_1,\;\ldots,\;f_{m-1}$ полинома $f(x)$ лежат в поле $\Bbb{F}_q$, а сам полином является неприводимым над этим полем.

Можно установить такое следствие из Теоремы 2. Из свойства конечных полей, говорящего о том, что все ненулевые элементы поля $\Bbb{F}_Q$ являются корнями многочлена $x^{Q-1}-1$, можно заключить, что многочлен $x^{Q-1}-1$ можно разложить на неприводимые над полем $\Bbb{F}_q$ многочлены $f_0(x),\;f_1(x),\;\ldots,\;f_d$, каждый из которых соответствует своему циклотомичесому классу.

См. также

• Конечное поле

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставить интервики в рамках проекта Интервики.