хуита

2.3 Арифметика полиномов, заданных над конечным полем

Рассмотрим полином

в котором коэффициенты являются элементами поля .

Введем основные правила арифметических действий с формальными полиномами, коэффициенты которого принадлежат полю (подобные полиномы обычно называют полиномами над).

Суммой двух полиномов и называется полином, определяемый соотношением:

Умножение полинома на скаляр (где ) осуществляется как

Установив операции сложения полиномов и умножения полинома на скаляр, можно сказать, что множество полиномов кодовых слов обладает структурой векторного пространства и для него справедливы утверждения:

– если , то ;

– если , то .

Рассмотрим некоторые определения, связанные с полиномами, заданными над конечным полем.

Пусть имеется многочлен .

Приведенным (или нормированным) полиномом называется полином, старший коэффициент которого .

Нулевым полиномом называется полином.

Степенью ненулевого полинома называется наибольшая степень формальной переменной при ненулевом коэффициенте и обозначается как .

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

Если и , то

где .

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

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

где неотрицательное целое , меньшее , называется остатком (от деления на), называется частным от деления, – делимым, а – делителем.

Поскольку в кольце полиномов определена операция умножения, то, поступая аналогично, можно ввести операцию деления полиномов с остатком. Однако, для полиномов сравнение в терминах «больше–меньше» невозможно, поэтому для получения остатка сравниваются степени полиномов. Возьмем полином и представим произвольный полином как

В данном соотношении, возможном для любых и , назовем полиномы , , и делимым, делителем, частным и остатком соответственно. Операция деления полиномов известна под названием алгоритма Евклида. Определение частного и остатка от деления полиномов осуществляется «в столбик», как и при делении целых чисел.

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

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

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

Полином, который не может быть разложен на множители меньшей степени, называется неприводимым.

Наибольшим общим делителем двух полиномов и , обозначаемым как , называется приведенный полином наибольшей степени, делящий одновременно оба из них.

Наименьшим общим кратным двух полиномов и , обозначаемым как , называется приведенный полином наименьшей степени, делящийся на оба из них.

Если наибольший общий делитель двух полиномов равен единицы, т.е. , то они называются взаимно простыми.

Содержание