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

Многочленом над конечным полем называется формальная сумма вида

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

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

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

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

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

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

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

 

Таким образом, корни многочлена   также являются корнями двучлена  [10].

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

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

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

Если   суть корни  , то

 

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

 

Тогда коэффициенты   полинома   лежат в поле  , а сам полином является неприводимым над этим полем.

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

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

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

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

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

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

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

 

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

Среди многочленов над конечными полями особо выделяют многочлены Жегалкина. Они представляют собой полиномы многих переменных над полем  [17].

 

С помощью такого полинома можно задать любую булеву функцию[18]  , причем единственным образом[17][19].

ПрименениеПравить

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

Также многочлены над конечными полями используются в современном помехоустойчивом кодировании[20] (для описания циклических кодов[21] и для декодирования кода Рида — Соломона с помощью алгоритма Евклида[22]), генераторах псевдослучайных чисел[23] (реализуются при помощи регистров сдвига)[24], поточном шифровании[25] и алгоритмах проверки целостности данных.

См. такжеПравить

ПримечанияПравить

ЛитератураПравить