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

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

$f(x)=f_0+f_{1}x+\dots +f_m{x}^m,f_i\in {𝔽}_q,f_m\ne 0.$

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

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

$x^0\equiv 1.$

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

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

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

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

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

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

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

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

$x^Q-x=\prod _{\alpha \in {𝔽}_Q}(x-\alpha )$

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

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

Шаблон:Рамка Остаток от деления $f(x)$ на $(x-a)$ равен $f(a)$. Шаблон:Конец рамки

Шаблон:Рамка Если $x_0$ — корень $f(x)$, то $(x-x_0)$ делит $f(x)$. Шаблон:Конец рамки

Шаблон:Рамка Если $x_1,\dots ,x_m$ суть корни $f(x)$, то

$f(x)=a(x-x_1)(x-x_2)\dots (x-x_m).$

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

Шаблон:Рамка Теорема 1. Если $x_0$ — корень $f(x)$, то $x_0^q$ — тоже корень $f(x)$Шаблон:Sfn. Шаблон:Конец рамки

Шаблон:Рамка Теорема 2. Сопряженные элементы поля Галуа имеют один и тот же порядокШаблон:Sfn. Шаблон:Конец рамки

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

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

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

Если $\alpha$ — примитивный элементШаблон:Sfn (такой элемент, что ${\alpha }^{Q-1}=1$ и ${\alpha }^k\ne 1$ при $0<k<Q-1$) поля ${𝔽}_Q,Q=q^m$, то циклотомический класс $C=\{\alpha ,{\alpha }^q,{\alpha }^{q^2},\dots ,{\alpha }^{q^{m-1}}\}$ над полем ${𝔽}_q$ будет иметь ровно $m$ элементов.

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

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

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

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

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

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

Связь с корнями полиномов

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

Шаблон:Рамка Теорема 3. Пусть $\alpha ,{\alpha }^q,{\alpha }^{q^2},\dots ,{\alpha }^{q^{m-1}}$ циклотомический класс, порожденный элементом $\alpha \in {𝔽}_{q^l}$ и полином $f(x)=f_0+f_{1}x+f_2{x}^2+\dots +f_{m-1}{x}^{m-1}+x^m$ имеет в качестве своих корней элементы этого циклотомического класса, то есть

$f(x)=(x-\alpha )(x-{\alpha }^q)\dots (x-{\alpha }^{q^{m-1}}).$

Тогда коэффициенты $f_0,f_1,\dots ,f_{m-1}$ полинома $f(x)$ лежат в поле ${𝔽}_q$, а сам полином является неприводимым над этим полем. Шаблон:Конец рамки

Можно установить такое следствие из Теоремы 3. Из свойства конечных полей, говорящего о том, что все ненулевые элементы поля ${𝔽}_Q$ являются корнями многочлена $x^{Q-1}-1$, можно заключить, что многочлен $x^{Q-1}-1$ можно разложить на неприводимые над полем ${𝔽}_q$ многочлены $f_0(x),f_1(x),\dots ,f_d$, каждый из которых соответствует своему циклотомическому классуШаблон:Sfn.

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

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

Шаблон:Рамка Определение. Порядок корней неприводимого многочлена называется показателем, к которому этот многочлен принадлежит. Неприводимый многочлен называется примитивным, если все его корни являются порождающими элементами мультипликативной группы поляШаблон:Sfn. Шаблон:Конец рамки Все корни примитивного многочлена имеют порядок, равный порядку мультипликативной группы расширенного поля ${𝔽}_Q$, то есть $Q-1$Шаблон:Sfn.

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

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

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

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

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

$f(x_1,x_2,\dots ,x_N)=a+\sum _{1⩽i⩽N}{a}_i{x}_i+\sum _{1⩽i<j⩽N}{a}_{i,j}{x}_i{x}_j+\sum _{1⩽i<j<k⩽N}{a}_{i,j,k}{x}_i{x}_j{x}_k+\dots +a_{1,2,\dots ,N}{x}_1{x}_2\dots x_N$

С помощью такого полинома можно задать любую булеву функциюШаблон:Sfn $f(x_1,x_2,\dots ,x_N)$, причем единственным образомШаблон:SfnШаблон:Sfn.

Применение

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.