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

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

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

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

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

${\displaystyle x^{0}\equiv 1.}$

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

Любую функцию над конечным полем можно задать с помощью некоторого многочлена (например, интерполяционного многочлена Лагранжа).

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

  ${\displaystyle f(x)=t(x)h(x)+r(x).}$

  • Если степень ${\displaystyle r(x)}$ строго меньше степени ${\displaystyle h(x)}$, то такое соотношение называется представлением полинома ${\displaystyle f(x)}$ в виде частного и остатка от деления ${\displaystyle f(x)}$ на ${\displaystyle h(x)}$, причем такое представление единственно^[3]. Ясно, что ${\displaystyle f(x)-r(x)}$ делится без остатка на ${\displaystyle h(x)}$, что записывается как ${\displaystyle f(x)\equiv r(x){\pmod {h(x)}}}$^[4].
  • Если ${\displaystyle r(x)=0}$, то полином ${\displaystyle h(x)}$ называется делителем полинома ${\displaystyle f(x)}$^[5].
• Полином является неприводимым над полем ${\displaystyle \mathbb {F} _{q}}$, если он не имеет нетривиальных делителей (степени большей 0 и меньшей ${\displaystyle \deg(f(x))}$)^[5][6].
• Расширением поля ${\displaystyle GF(q)}$ называется множество ${\displaystyle F[x]_{/(p(x))}}$ классов вычетов по модулю неприводимого многочлена ${\displaystyle p(x)}$ над полем ${\displaystyle GF(q)}$^[6].
• Минимальным многочленом (минимальной функцией) для элемента ${\displaystyle \beta }$ из расширенного поля называется такой нормированный многочлен ${\displaystyle m(x)}$ над ${\displaystyle GF(q)}$ минимальной степени, что ${\displaystyle m(\beta )=0}$^[7][8].
• Корнем многочлена называется всякий элемент поля, значение этого многочлена на котором равно нулю.
• Сопряженными называются элементы поля, являющиеся корнями одного и того же неприводимого многочлена^[9].

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

Среди многочленов над конечными полями особо выделяют многочлены Жегалкина. Они представляют собой полиномы многих переменных над полем ${\displaystyle GF(2)}$^[17].

${\displaystyle 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}}$

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

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

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

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

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

• Акритас А. Основы компьютерной алгебры с приложениями / пер. с англ. Е. В. Панкратьева. — М.: Мир, 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.