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

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

$f(x)=f_0+f_{1}x+\dots <!--\; \dots \; -->+f_m{x}^m,f_i\in <!--\; \in \; -->{\mathbb{F}}_q,f_m\ne <!--\; \ne \; -->0.$$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$$m$ — целое неотрицательное число, называемое степенью многочлена $f(x)$$f(x)$, а $x^k,k\in <!--\; \in \; -->{\mathbb{N}}_0$$x^k, k\in \mathbb N_0$ — элементы алгебры над ${\mathbb{F}}_q,$$\mathbb {F} _{q},$ умножение которых задаётся правилами:

$x^k\cdot <!--\; \cdot \; -->x^m=x^{k+m},$$x^k \cdot x^m = x^{k+m},$

$x^0\equiv <!--\; \equiv \; -->1.$$x^0 \equiv 1.$

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

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

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

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

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

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

Корни многочленаПравить

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

$x^Q-<!--\; -\; -->x=\underset{\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->{\mathbb{F}}_Q}{\prod <!--\; \prod \; -->}(x-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->})$$x^{Q}-x=\prod _{\alpha \in \mathbb {F} _{Q}}{(x-\alpha )}$ 

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

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

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

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

Если $x_1,\dots <!--\; \dots \; -->,x_m$$x_1,\;\ldots,\;x_m$  — корни $f(x)$$f(x)$ , то $f(x)=a(x-<!--\; -\; -->x_1)(x-<!--\; -\; -->x_2)\dots <!--\; \dots \; -->(x-<!--\; -\; -->x_m).$$f(x) = a(x-x_1)(x-x_2)\ldots(x-x_m).$

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

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

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

Циклотомический классПравить

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

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

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

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

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

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

$\begin{array}{c}\{1\},\\ \{\mathrm{\alpha <!--\; \alpha \; -->},{\mathrm{\alpha <!--\; \alpha \; -->}}^2,{\mathrm{\alpha <!--\; \alpha \; -->}}^4\},\\ \{{\mathrm{\alpha <!--\; \alpha \; -->}}^3,{\mathrm{\alpha <!--\; \alpha \; -->}}^6,{\mathrm{\alpha <!--\; \alpha \; -->}}^5\}.\end{array}$$\begin{matrix} \{1\}, \\ \{\alpha,\;\alpha^2,\;\alpha^4\}, \\ \{\alpha^3,\;\alpha^6,\;\alpha^5\}. \end{matrix}$ 

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

$\begin{array}{c}\{1\},\\ \{\mathrm{\alpha <!--\; \alpha \; -->},{\mathrm{\alpha <!--\; \alpha \; -->}}^4\},\{{\mathrm{\alpha <!--\; \alpha \; -->}}^2,{\mathrm{\alpha <!--\; \alpha \; -->}}^8\},\\ \{{\mathrm{\alpha <!--\; \alpha \; -->}}^3,{\mathrm{\alpha <!--\; \alpha \; -->}}^{12}\},\{{\mathrm{\alpha <!--\; \alpha \; -->}}^5\},\{{\mathrm{\alpha <!--\; \alpha \; -->}}^{10}\},\\ \{{\mathrm{\alpha <!--\; \alpha \; -->}}^6,{\mathrm{\alpha <!--\; \alpha \; -->}}^9\},\{{\mathrm{\alpha <!--\; \alpha \; -->}}^7,{\mathrm{\alpha <!--\; \alpha \; -->}}^{13}\},\\ \{{\mathrm{\alpha <!--\; \alpha \; -->}}^{11},{\mathrm{\alpha <!--\; \alpha \; -->}}^{14}\}.\end{array}$$\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$$x^{Q-1}-1$  на неприводимые полиномы над полем ${\mathbb{F}}_q$$\mathbb {F} _{q}$ .

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

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

Виды многочленовПравить

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

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

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

Круговые многочленыПравить

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

$x^{q^m-<!--\; -\; -->1}-<!--\; -\; -->1=\underset{d\mid <!--\; \mid \; -->q^m-<!--\; -\; -->1}{\prod <!--\; \prod \; -->}{\mathrm{\psi <!--\; \psi \; -->}}_d(x)$$x^{q^{m}-1}-1=\prod _{d\,\mid \,q^{m}-1}\psi _{d}(x)$ 

Многочлены ЖегалкинаПравить

Среди многочленов над конечными полями особо выделяют многочлены Жегалкина. Они представляют собой полиномы многих переменных над полем $GF(2)$$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,\dots <!--\; \dots \; -->,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.