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

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

$f(x)=f_{0}+f_{1}x+\ldots +f_{m}x^{m},\quad f_{i}\in \mathbb {F} _{q},\quad f_{m}\neq 0.$

Здесь $m$ — целое неотрицательное число, называемое степенью многочлена $f(x)$, а $x^{k},k\in \mathbb {N} _{0}$ — элементы алгебры над $\mathbb {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}$ при старшей степени.
• Сумма и произведение полиномов определены обычным образом, а операции с коэффициентами осуществляются в поле $\mathbb {F} _{q}$.
• Для двух полиномов $f(x)$ и $h(x)\neq 0$ всегда найдутся полиномы $t(x)$ и $r(x)$ над полем $\mathbb {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)}}$.
  • Если $r(x)=0$, то полином $h(x)$ называется делителем полинома $f(x)$.
• Полином является неприводимым над полем $\mathbb {F} _{q}$, если он не имеет нетривиальных делителей (степени большей 0 и меньшей $\deg(f(x))$).
• Расширением поля $GF(q)$ называется множество $F[x]_{/(p(x))}$ классов вычетов по модулю неприводимого многочлена $p(x)$ над полем $GF(q)$.
• Минимальным многочленом (минимальной функцией) для элемента $\beta$ из расширенного поля называется такой нормированный многочлен $m(x)$ над $GF(q)$ минимальной степени, что $m(\beta )=0$.
• Корнем многочлена называется всякий элемент поля, значение этого многочлена на котором равно нулю.
• Сопряженными называются элементы поля, являющиеся корнями одного и того же неприводимого многочлена.

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

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

$x^{Q}-x=\prod _{\alpha \in \mathbb {F} _{Q}}{(x-\alpha )}$

Таким образом, корни многочлена $f(x)$ также являются корнями двучлена $x^{Q}-x$.

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

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

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

Если $x_{1},\;\ldots ,\;x_{m}$ суть корни $f(x)$, то $f(x)=a(x-x_{1})(x-x_{2})\ldots (x-x_{m}).$

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

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

Теорема 2. Сопряженные элементы поля Галуа имеют один и тот же порядок.

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

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

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

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

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

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

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

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

Пример 2. Аналогично можно построить классы на поле $\mathbb {F} _{16}$ над полем $\mathbb {F} _{4}$, то есть $q=4,\;Q=q^{2}=16$. Пусть $\alpha$ — примитивный элемент поля $\mathbb {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$ на неприводимые полиномы над полем $\mathbb {F} _{q}$.

Теорема 3. Пусть $\alpha ,\;\alpha ^{q},\;\alpha ^{q^{2}},\;\ldots ,\;\alpha ^{q^{m-1}}$ циклотомический класс, порожденный элементом $\alpha \in \mathbb {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)$ лежат в поле $\mathbb {F} _{q}$, а сам полином является неприводимым над этим полем.

Можно установить такое следствие из Теоремы 3. Из свойства конечных полей, говорящего о том, что все ненулевые элементы поля $\mathbb {F} _{Q}$ являются корнями многочлена $x^{Q-1}-1$, можно заключить, что многочлен $x^{Q-1}-1$ можно разложить на неприводимые над полем $\mathbb {F} _{q}$ многочлены $f_{0}(x),\;f_{1}(x),\;\ldots ,\;f_{d}$, каждый из которых соответствует своему циклотомическому классу.

Виды многочленов

Примитивные многочлены

Определение. Порядок корней неприводимого многочлена называется показателем, к которому этот многочлен принадлежит. Неприводимый многочлен называется примитивным, если все его корни являются порождающими элементами мультипликативной группы поля.

Все корни примитивного многочлена имеют порядок, равный порядку мультипликативной группы расширенного поля $\mathbb {F} _{Q}$, то есть $Q-1$.

Круговые многочлены

Пусть $\alpha$ есть порождающий элемент мультипликативной группы поля $GF(q^{m})$, и её порядок равен $n=q^{m}-1$, то есть $\alpha ^{q^{m}-1}=1$. Пусть все элементы порядка $d$ являются корнями многочлена $\psi _{d}(x),\;n\,\vdots \,d$. Тогда такой многочлен называется круговым и верно равенство:

$x^{q^{m}-1}-1=\prod _{d\,\mid \,q^{m}-1}\psi _{d}(x)$

Многочлены Жегалкина

Среди многочленов над конечными полями особо выделяют многочлены Жегалкина. Они представляют собой полиномы многих переменных над полем $GF(2)$.

$f(x_{1},\;x_{2},\;\ldots ,\;x_{N})=a+\sum _{1\leqslant i\leqslant N}a_{i}x_{i}+\sum _{1\leqslant i<j\leqslant N}a_{i,j}x_{i}x_{j}+\sum _{1\leqslant i<j<k\leqslant N}a_{i,\;j,\;k}x_{i}x_{j}x_{k}+\ldots +a_{1,\;2,\;\ldots ,\;N}x_{1}x_{2}\ldots x_{N}$

С помощью такого полинома можно задать любую булеву функцию $f(x_{1},\;x_{2},\;\ldots ,\;x_{N})$, причем единственным образом.

Применение

Существует множество алгоритмов, использующих многочлены над конечными полями и кольцами.

• Алгоритм Евклида
• Алгоритм Берлекэмпа
• Алгоритм Берлекэмпа — Мэсси
• Метод Берлекэмпа
• Код Боуза — Чоудхури — Хоквингема
• Код Рида — Соломона
• CRC
• Тест Агравала — Каяла — Саксены
• Схема разделения секрета Шамира

Также многочлены над конечными полями используются в современном помехоустойчивом кодировании (для описания циклических кодов и для декодирования кода Рида — Соломона с помощью алгоритма Евклида), генераторах псевдослучайных чисел (реализуются при помощи регистров сдвига), поточном шифровании и алгоритмах проверки целостности данных.

См. также

• Многочлен
• Конечное поле
• Кольцо многочленов

Литература

• Акритас А. Основы компьютерной алгебры с приложениями / пер. с англ. Е. В. Панкратьева. — М.: Мир, 1994. — 544 с.
• Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии: Учебное пособие — 3-е изд., испр. и доп. — М.: Гелиос АРВ, 2005. — 480 с. — ISBN 978-5-85438-137-6
• Блейхут Р. Э. Теория и практика кодов, контролирующих ошибки / под ред. К. Ш. Зигангирова, пер. пер. с англ. И.И.Грушко, В. М. Блиновского — М.: Мир, 1986. — 576 с.
• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
• Сагалович Ю. Л. Введение в алгебраические коды — 3-е изд., перераб. и доп. — М.: ИППИ РАН, 2014. — 310 с. — ISBN 978-5-901158-24-1
• Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов — 2-е изд., перераб. и доп. — М.: Наука, 1986. — 384 с.
• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.