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

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

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

Остаток от деления ${\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)}$[11].

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

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

Следствием Теоремы 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 \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}}$, каждый из которых соответствует своему циклотомическому классу^[14].

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

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

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

Все корни примитивного многочлена имеют порядок, равный порядку мультипликативной группы расширенного поля ${\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] и алгоритмах проверки целостности данных.

См. также

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

Примечания

1. Акритас, 1994, с. 146.
2. Блейхут, 1986, с. 88.
3. Блейхут, 1986, с. 90.
4. Блейхут, 1986, с. 91.
5. Блейхут, 1986, с. 89.
6. Сагалович, 2014, с. 79.
7. Сагалович, 2014, с. 93.
8. Блейхут, 1986, с. 104.
9. Сагалович, 2014, с. 101.
10. Сагалович, 2014, с. 82.
11. Сагалович, 2014, с. 96.
12. Сагалович, 2014, с. 105.
13. Блейхут, 1986, с. 99.
14. Сагалович, 2014, с. 97.
15. Блейхут, 1986, с. 103.
16. Сагалович, 2014, с. 102.
17. Яблонский, 1986, с. 32.
18. Яблонский, 1986, с. 12.
19. Габидулин, Кшевецкий, Колыбельников, 2011, с. 81.
20. Сагалович, 2014, с. 169—172.
21. Блейхут, 1986, с. 116—121.
22. Блейхут, 1986, с. 223—228.
23. Габидулин, Кшевецкий, Колыбельников, 2011, с. 77—83.
24. Алферов, Зубов, Кузьмин и др., 2005, с. 251—260.
25. Габидулин, Кшевецкий, Колыбельников, 2011, с. 74—83.

Литература

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