Русская Википедия:Многочлен над конечным полем
Многочленом <math>f(x)</math> над конечным полем <math>\mathbb{F}_q</math> называется формальная сумма вида
- <math>f(x)=f_0+f_1 x+\ldots+f_m x^m,\quad f_i\in \mathbb{F}_q,\quad f_m\neq 0.</math>
Здесь <math>m</math> — целое неотрицательное число, называемое степенью многочлена <math>f(x)</math>, а <math>x^k, k\in \mathbb N_0</math> — элементы алгебры над <math>\mathbb{F}_q,</math> умножение которых задаётся правилами:
- <math>x^k \cdot x^m = x^{k+m},</math>
- <math>x^0 \equiv 1.</math>
Такое определение позволяет умножать многочлены формально, не заботясь о том, что разные степени одного и того же элемента конечного поля могут совпадатьШаблон:SfnШаблон:Sfn.
Любую функцию над конечным полем можно задать с помощью некоторого многочлена (например, интерполяционного многочлена Лагранжа).
Связанные определения
- Число <math>m\geqslant 0</math> называется степенью полинома и обозначается как <math>\deg(f(x))</math>Шаблон:Sfn.
- Если <math>f_m=1</math>, то полином называется нормированным (приведённым)Шаблон:Sfn. Полином всегда можно нормировать делением его на коэффициент <math>f_m</math> при старшей степени.
- Сумма и произведение полиномов определены обычным образом, а операции с коэффициентами осуществляются в поле <math>\mathbb{F}_q</math>.
- Для двух полиномов <math>f(x)</math> и <math>h(x)\ne 0</math> всегда найдутся полиномы <math>t(x)</math> и <math>r(x)</math> над полем <math>\mathbb{F}_q</math>, что будет выполняться соотношение
- <math>f(x)=t(x)h(x)+r(x).</math>
- Если степень <math>r(x)</math> строго меньше степени <math>h(x)</math>, то такое соотношение называется представлением полинома <math>f(x)</math> в виде частного и остатка от деления <math>f(x)</math> на <math>h(x)</math>, причем такое представление единственноШаблон:Sfn. Ясно, что <math>f(x)-r(x)</math> делится без остатка на <math>h(x)</math>, что записывается как <math>f(x)\equiv r(x)\pmod{h(x)}</math>Шаблон:Sfn.
- Если <math>r(x)=0</math>, то полином <math>h(x)</math> называется делителем полинома <math>f(x)</math>Шаблон:Sfn.
- Полином является неприводимым над полем <math>\mathbb{F}_q</math>, если он не имеет нетривиальных делителей (степени большей 0 и меньшей <math>\deg(f(x))</math>)Шаблон:SfnШаблон:Sfn.
- Расширением поля <math>GF(q)</math> называется множество <math>F[x]_{/(p(x))}</math> классов вычетов по модулю неприводимого многочлена <math>p(x)</math> над полем <math>GF(q)</math>Шаблон:Sfn.
- Минимальным многочленом (минимальной функцией) для элемента <math>\beta</math> из расширенного поля называется такой нормированный многочлен <math>m(x)</math> над <math>GF(q)</math> минимальной степени, что <math>m(\beta)=0</math>Шаблон:SfnШаблон:Sfn.
- Корнем многочлена называется всякий элемент поля, значение этого многочлена на котором равно нулю.
- Сопряженными называются элементы поля, являющиеся корнями одного и того же неприводимого многочленаШаблон:Sfn.
Корни многочлена
Полином степени m имеет ровно m корней (с учётом кратности), принадлежащих некоторому расширенному полю <math>\mathbb{F}_Q,\quad \mathbb{F}_q\subseteq \mathbb{F}_Q</math>. Если <math>q=p^s</math>, где <math>p</math> — простое, то <math>Q=p^S,\;S\geqslant s</math>. Исходя из свойств конечных полей, любой элемент поля <math>\mathbb{F}_Q</math> является корнем двучлена <math>x^Q-x</math>:
- <math>x^Q-x=\prod_{\alpha\in\mathbb{F}_Q}{(x-\alpha)}</math>
Таким образом, корни многочлена <math>f(x)</math> также являются корнями двучлена <math>x^Q-x</math>Шаблон:Sfn.
Справедливы теорема Безу и следствия из неё:
Шаблон:Рамка Остаток от деления <math>f(x)</math> на <math>(x-a)</math> равен <math>f(a)</math>. Шаблон:Конец рамки
Шаблон:Рамка Если <math>x_0</math> — корень <math>f(x)</math>, то <math>(x-x_0)</math> делит <math>f(x)</math>. Шаблон:Конец рамки
Шаблон:Рамка Если <math>x_1,\;\ldots,\;x_m</math> — корни <math>f(x)</math>, то
- <math>f(x) = a(x-x_1)(x-x_2)\ldots(x-x_m).</math>
Также справедливы следующие теоремы:
Шаблон:Рамка Теорема 1. Если <math>x_0</math> — корень <math>f(x)</math>, то <math>x_0^q</math> — тоже корень <math>f(x)</math>Шаблон:Sfn. Шаблон:Конец рамки
Шаблон:Рамка Теорема 2. Сопряженные элементы поля Галуа имеют один и тот же порядокШаблон:Sfn. Шаблон:Конец рамки
Циклотомический класс
Следствием Теоремы 1 может быть тот факт, что, если <math>\alpha\in\mathbb{F}_Q</math> — корень полинома <math>f(x)</math> над полем <math>\mathbb{F}_q</math>, то и <math>\alpha^q,\;\alpha^{q^2},\;\alpha^{q^3},\;\ldots\in\mathbb{F}_Q</math> являются его корнями.
Определение: циклотомическим классом над полем <math>\mathbb{F}_q,\;q=p^s</math>, порождённым некоторым элементом <math>\alpha\in\mathbb{F}_Q,\;Q=p^S</math> называется множество всех различных элементов <math>\mathbb{F}_Q</math>, являющихся <math>q</math>-ми степенями <math>\alpha</math>Шаблон:Sfn.
Если <math>\alpha</math> — примитивный элементШаблон:Sfn (такой элемент, что <math>\alpha^{Q-1}=1</math> и <math>\alpha^k\neq 1</math> при <math>0<k<Q-1</math>) поля <math>\mathbb{F}_Q,\;Q=q^m</math>, то циклотомический класс <math>C=\{\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}\}</math> над полем <math>\mathbb{F}_q</math> будет иметь ровно <math>m</math> элементов.
Следует отметить, что любой элемент из циклотомического класса может порождать этот и только этот класс, а, следовательно, и принадлежать только ему.
Примеры циклотомических классов
Пример 1. Пусть <math>q=2</math>, <math>Q=2^3=8</math> и <math>\alpha</math> — примитивный элемент поля <math>\mathbb{F}_8</math>, то есть <math>\alpha^7=1</math> и <math>\alpha^i\neq 1</math> при <math>i<7</math>. Учитывая также, что <math>\alpha^8=\alpha</math>, можно получить разложение всех ненулевых элементов поля <math>\mathbb{F}_8</math> на три циклотомических класса над полем <math>\mathbb{F}_2</math>:
- <math>\begin{matrix}
\{1\}, \\ \{\alpha,\;\alpha^2,\;\alpha^4\}, \\ \{\alpha^3,\;\alpha^6,\;\alpha^5\}. \end{matrix}</math>
Пример 2. Аналогично можно построить классы на поле <math>\mathbb{F}_{16}</math> над полем <math>\mathbb{F}_4</math>, то есть <math>q=4,\;Q=q^2=16</math>. Пусть <math>\alpha</math> — примитивный элемент поля <math>\mathbb{F}_{16}</math>, значит <math>\alpha^{15}=1,\;\alpha^{16}=\alpha</math>.
- <math>\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}</math>
Связь с корнями полиномов
Следующая Теорема устанавливает связь между циклотомическими классами и разложением полинома <math>x^{Q-1}-1</math> на неприводимые полиномы над полем <math>\mathbb{F}_q</math>.
Шаблон:Рамка Теорема 3. Пусть <math>\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}</math> циклотомический класс, порожденный элементом <math>\alpha\in \mathbb{F}_{q^l}</math> и полином <math>f(x)=f_0+f_1 x+f_2 x^2+\ldots+f_{m-1}x^{m-1}+x^m</math> имеет в качестве своих корней элементы этого циклотомического класса, то есть
- <math>f(x)=(x-\alpha)(x-\alpha^q)\ldots(x-\alpha^{q^{m-1}}).</math>
Тогда коэффициенты <math>f_0,\;f_1,\;\ldots,\;f_{m-1}</math> полинома <math>f(x)</math> лежат в поле <math>\mathbb{F}_q</math>, а сам полином является неприводимым над этим полем. Шаблон:Конец рамки
Можно установить такое следствие из Теоремы 3. Из свойства конечных полей, говорящего о том, что все ненулевые элементы поля <math>\mathbb{F}_Q</math> являются корнями многочлена <math>x^{Q-1}-1</math>, можно заключить, что многочлен <math>x^{Q-1}-1</math> можно разложить на неприводимые над полем <math>\mathbb{F}_q</math> многочлены <math>f_0(x),\;f_1(x),\;\ldots,\;f_d</math>, каждый из которых соответствует своему циклотомическому классуШаблон:Sfn.
Виды многочленов
Примитивные многочлены
Шаблон:Рамка Определение. Порядок корней неприводимого многочлена называется показателем, к которому этот многочлен принадлежит. Неприводимый многочлен называется примитивным, если все его корни являются порождающими элементами мультипликативной группы поляШаблон:Sfn. Шаблон:Конец рамки Все корни примитивного многочлена имеют порядок, равный порядку мультипликативной группы расширенного поля <math>\mathbb{F}_Q</math>, то есть <math>Q-1</math>Шаблон:Sfn.
Круговые многочлены
Пусть <math>\alpha</math> есть порождающий элемент мультипликативной группы поля <math>GF(q^m)</math>, и её порядок равен <math>n=q^m-1</math>, то есть <math>\alpha^{q^m-1}=1</math>. Пусть все элементы порядка <math>d</math> являются корнями многочлена <math>\psi_d(x),\;n\,\vdots\,d</math>. Тогда такой многочлен называется круговым и верно равенствоШаблон:Sfn:
- <math>x^{q^m-1}-1=\prod_{d\,\mid\,q^m-1}\psi_d(x)</math>
Многочлены Жегалкина
Среди многочленов над конечными полями особо выделяют многочлены Жегалкина. Они представляют собой полиномы многих переменных над полем <math>GF(2)</math>Шаблон:Sfn.
- <math>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}</math>
С помощью такого полинома можно задать любую булеву функциюШаблон:Sfn <math>f(x_1,\;x_2,\;\ldots,\;x_N)</math>, причем единственным образомШаблон:SfnШаблон:Sfn.
Применение
Существует множество алгоритмов, использующих многочлены над конечными полями и кольцами.
- Алгоритм Евклида
- Алгоритм Берлекэмпа
- Алгоритм Берлекэмпа — Мэсси
- Метод Берлекэмпа
- Код Боуза — Чоудхури — Хоквингема
- Код Рида — Соломона
- CRC
- Тест Агравала — Каяла — Саксены
- Схема разделения секрета Шамира
Также многочлены над конечными полями используются в современном помехоустойчивом кодированииШаблон:Sfn (для описания циклических кодовШаблон:Sfn и для декодирования кода Рида — Соломона с помощью алгоритма ЕвклидаШаблон:Sfn), генераторах псевдослучайных чиселШаблон:Sfn (реализуются при помощи регистров сдвига)Шаблон:Sfn, поточном шифрованииШаблон:Sfn и алгоритмах проверки целостности данных.
См. также
Примечания
Литература
- Шаблон:Книга
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source
- Шаблон:Source
- Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.
