Многочленом ${\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.}$

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

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

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

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

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

Полином степени 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}$ .

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

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

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

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

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

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

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

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

Следствием Теоремы 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 }$ .

Если ${\displaystyle \alpha }$ — примитивный элемент (такой элемент, что ${\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 \alpha ,\;\alpha ^{q},\;\alpha ^{q^{2}},\;\ldots ,\;\alpha ^{q^{m-1}}}$ циклотомический класс, порожденный элементом ${\displaystyle \alpha \in \mathbb {F} _{q^{l}}}$ и полином ${\displaystyle f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\ldots +f_{m-1}x^{m-1}+x^{m}}$ имеет в качестве своих корней элементы этого циклотомического класса, то есть ${\displaystyle f(x)=(x-\alpha )(x-\alpha ^{q})\ldots (x-\alpha ^{q^{m-1}}).}$ Тогда коэффициенты ${\displaystyle f_{0},\;f_{1},\;\ldots ,\;f_{m-1}}$ полинома ${\displaystyle f(x)}$ лежат в поле ${\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}}$ , каждый из которых соответствует своему циклотомическому классу .

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

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

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

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

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

Пусть ${\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}$ . Тогда такой многочлен называется круговым и верно равенство :

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

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

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

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

С помощью такого полинома можно задать любую булеву функцию ${\displaystyle 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.