Многочленом над конечным полем называется формальная сумма вида
Здесь — целое неотрицательное число, называемое степенью многочлена , а — элементы алгебры над умножение которых задаётся правилами:
Такое определение позволяет умножать многочлены формально, не заботясь о том, что разные степени одного и того же элемента конечного поля могут совпадать.
Любую функцию над конечным полем можно задать с помощью некоторого многочлена (например, интерполяционного многочлена Лагранжа).
Связанные определения Число называется степенью полинома и обозначается как . Если , то полином называется нормированным (приведённым). Полином всегда можно нормировать делением его на коэффициент при старшей степени. Сумма и произведение полиномов определены обычным образом, а операции с коэффициентами осуществляются в поле . Для двух полиномов и всегда найдутся полиномы и над полем , что будет выполняться соотношение
Если степень строго меньше степени , то такое соотношение называется представлением полинома в виде частного и остатка от деления на , причем такое представление единственно. Ясно, что делится без остатка на , что записывается как . Если , то полином называется делителем полинома . Полином является неприводимым над полем , если он не имеет нетривиальных делителей (степени большей 0 и меньшей ). Расширением поля называется множество классов вычетов по модулю неприводимого многочлена над полем . Минимальным многочленом (минимальной функцией) для элемента из расширенного поля называется такой нормированный многочлен над минимальной степени, что . Корнем многочлена называется всякий элемент поля, значение этого многочлена на котором равно нулю. Сопряженными называются элементы поля, являющиеся корнями одного и того же неприводимого многочлена.
Корни многочлена Полином степени m имеет ровно m корней (с учётом кратности), принадлежащих некоторому расширенному полю . Если , где — простое, то . Исходя из свойств конечных полей, любой элемент поля является корнем двучлена :
Таким образом, корни многочлена также являются корнями двучлена .
Справедливы теорема Безу и следствия из неё:
Остаток от деления на равен .
Если — корень , то делит .
Если суть корни , то
Также справедливы следующие теоремы:
Теорема 1. Если — корень , то — тоже корень .
Теорема 2. Сопряженные элементы поля Галуа имеют один и тот же порядок.
Циклотомический класс Следствием Теоремы 1 может быть тот факт, что, если — корень полинома над полем , то и являются его корнями.
Определение: циклотомическим классом над полем , порождённым некоторым элементом называется множество всех различных элементов , являющихся -ми степенями .
Если — примитивный элемент (такой элемент, что и при ) поля , то циклотомический класс над полем будет иметь ровно элементов.
Следует отметить, что любой элемент из циклотомического класса может порождать этот и только этот класс, а, следовательно, и принадлежать только ему.
Примеры циклотомических классов Пример 1. Пусть , и — примитивный элемент поля , то есть и при . Учитывая также, что , можно получить разложение всех ненулевых элементов поля на три циклотомических класса над полем :
Пример 2. Аналогично можно построить классы на поле над полем , то есть . Пусть — примитивный элемент поля , значит .
Связь с корнями полиномов Следующая Теорема устанавливает связь между циклотомическими классами и разложением полинома на неприводимые полиномы над полем .
Теорема 3. Пусть циклотомический класс, порожденный элементом и полином имеет в качестве своих корней элементы этого циклотомического класса, то есть
Тогда коэффициенты полинома лежат в поле , а сам полином является неприводимым над этим полем.
Можно установить такое следствие из Теоремы 3. Из свойства конечных полей, говорящего о том, что все ненулевые элементы поля являются корнями многочлена , можно заключить, что многочлен можно разложить на неприводимые над полем многочлены , каждый из которых соответствует своему циклотомическому классу.
Виды многочленов
Примитивные многочлены
Определение. Порядок корней неприводимого многочлена называется показателем, к которому этот многочлен принадлежит. Неприводимый многочлен называется примитивным, если все его корни являются порождающими элементами мультипликативной группы поля.
Все корни примитивного многочлена имеют порядок, равный порядку мультипликативной группы расширенного поля , то есть .
Круговые многочлены Пусть есть порождающий элемент мультипликативной группы поля , и её порядок равен , то есть . Пусть все элементы порядка являются корнями многочлена . Тогда такой многочлен называется круговым и верно равенство:
Многочлены Жегалкина Среди многочленов над конечными полями особо выделяют многочлены Жегалкина. Они представляют собой полиномы многих переменных над полем .
С помощью такого полинома можно задать любую булеву функцию , причем единственным образом.
Применение Существует множество алгоритмов, использующих многочлены над конечными полями и кольцами. Алгоритм Евклида Алгоритм Берлекэмпа Алгоритм Берлекэмпа — Мэсси Метод Берлекэмпа Код Боуза — Чоудхури — Хоквингема Код Рида — Соломона CRC Тест Агравала — Каяла — Саксены Схема разделения секрета Шамира Также многочлены над конечными полями используются в современном помехоустойчивом кодировании (для описания циклических кодов и для декодирования кода Рида — Соломона с помощью алгоритма Евклида), генераторах псевдослучайных чисел (реализуются при помощи регистров сдвига), поточном шифровании и алгоритмах проверки целостности данных.
См. также Многочлен Конечное поле Кольцо многочленов
Примечания
Литература
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — : Мир, 1976. — С. 596.
Категория:Теория полей Категория:Многочлены