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

Многочленом  над конечным полем  называется формальная сумма вида
 
Здесь  — целое неотрицательное число, называемое степенью многочлена , а  — элементы алгебры над  умножение которых задаётся правилами:
 
 

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

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

Связанные определения 
 Число  называется степенью полинома и обозначается как .
 Если , то полином называется нормированным (приведённым). Полином всегда можно нормировать делением его на коэффициент  при старшей степени.
 Сумма и произведение полиномов определены обычным образом, а операции с коэффициентами осуществляются в поле .
 Для двух полиномов  и  всегда найдутся полиномы  и  над полем , что будет выполняться соотношение
 
 Если степень  строго меньше степени , то такое соотношение называется представлением полинома  в виде частного и остатка от деления  на , причем такое представление единственно. Ясно, что  делится без остатка на , что записывается как .
 Если , то полином  называется делителем полинома .
 Полином является неприводимым над полем , если он не имеет нетривиальных делителей (степени большей 0 и меньшей ).
 Расширением поля  называется множество  классов вычетов по модулю неприводимого многочлена  над полем .
 Минимальным многочленом (минимальной функцией) для элемента  из расширенного поля называется такой нормированный многочлен  над  минимальной степени, что .
 Корнем многочлена называется всякий элемент поля, значение этого многочлена на котором равно нулю.
 Сопряженными называются элементы поля, являющиеся корнями одного и того же неприводимого многочлена.

Корни многочлена 
Полином степени m имеет ровно m корней (с учётом кратности), принадлежащих некоторому расширенному полю . Если , где  — простое, то . Исходя из свойств конечных полей, любой элемент поля  является корнем двучлена :
 
Таким образом, корни многочлена  также являются корнями двучлена .

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

Остаток от деления  на  равен .

Если  — корень , то  делит .

Если  — корни , то
 

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

Теорема 1. Если  — корень , то  — тоже корень .

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

Циклотомический класс 
Следствием Теоремы 1 может быть тот факт, что, если  — корень полинома  над полем , то и  являются его корнями.

Определение: циклотомическим классом над полем , порождённым некоторым элементом  называется множество всех различных элементов , являющихся -ми степенями .

Если  — примитивный элемент (такой элемент, что  и  при ) поля , то циклотомический класс  над полем  будет иметь ровно  элементов.

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

Примеры циклотомических классов 
Пример 1. Пусть ,  и  — примитивный элемент поля , то есть  и  при . Учитывая также, что , можно получить разложение всех ненулевых элементов поля  на три циклотомических класса над полем :
 

Пример 2. Аналогично можно построить классы на поле  над полем , то есть . Пусть  — примитивный элемент поля , значит .

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

Теорема 3. Пусть  циклотомический класс, порожденный элементом  и полином  имеет в качестве своих корней элементы этого циклотомического класса, то есть
 
Тогда коэффициенты  полинома  лежат в поле , а сам полином является неприводимым над этим полем.

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

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

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

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

Все корни примитивного многочлена имеют порядок, равный порядку мультипликативной группы расширенного поля , то есть .

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

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

Применение 
Существует множество алгоритмов, использующих многочлены над конечными полями и кольцами.
 Алгоритм Евклида
 Алгоритм Берлекэмпа
 Алгоритм Берлекэмпа — Мэсси
Метод Берлекэмпа
 Код Боуза — Чоудхури — Хоквингема
 Код Рида — Соломона
 CRC
 Тест Агравала — Каяла — Саксены
 Схема разделения секрета Шамира
Также многочлены над конечными полями используются в современном помехоустойчивом кодировании (для описания циклических кодов и для декодирования кода Рида — Соломона с помощью алгоритма Евклида), генераторах псевдослучайных чисел (реализуются при помощи регистров сдвига), поточном шифровании и алгоритмах проверки целостности данных.

См. также 
 Многочлен
 Конечное поле
 Кольцо многочленов

Примечания

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

Общая алгебра
Теория полей
Многочлены