Глава 6. Разложение многочленов над конечными полями

6.1. Общий алгоритм

В этом разделе описывается один алгоритм разложения многочлена в произведение степеней неприводимых многочленов. Для достаточно малых этот алгоритм оказывается эффективным даже при больших числах

1. Строим -матрицу над строка которой соответствует многочлену приведенному по модулю . В частности,

Матрица может быть построена с помощью регистра сдвига, выполняющего умножение на х по модулю . В начальном положении в регистре записана 1 — первая строка матрицы После сдвигов в нем содержится вторая строка g и т. д. После сдвигов в регистре будет записана последняя строка матрицы .

Для произвольного многочлена степени над полем класс вычетов по модулю может быть определен с помощью умножения вектор-строки на матрицу Это вытекает из следующего соотношения:

Аналогично класс вычетов по модулю может быть найден путем умножения вектор-строки на матрицу — , где единичная -матрица над

2. Находим множество вектор-строк, образующих нуль-подпространство матрицы Для этого можно применить соответствующие операции над столбцами матрицы описанные в разд. 2.5, 2.6. Каждая вектор-строка из нуль-подпространства матрицы представима в виде многочлена удовлетворяющего сравнению наоборот, каждый многочлен удовлетворяющий этому сравнению, является представлением вектор-строки из нуль-подпространства матрицы

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

6.11. Теорема

Замечание. Если скаляр, то это разложение принимает вид

Если же многочлен ненулевой степени, то разложение (6.11) нетривиально. В общем случае это разложение является неполным, ибо н. о. д. может быть разложимым.

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

6.12. Пример. Пусть двоичный многочлен , иначе, Последовательные степени х имеют вид

(см. скан)

Если перенумеровать столбцы матрицы числами от 0 до 11 и прибавить третий столбец к шестому, первый, второй и четвертый столбцы к восьмому, а пятый столбец к десятому, то верхний правый восьмимерный квадрат матрицы можно сделать нулевым. Нижний правый квадрат при этом примет вид

Решениями уравнения являются , где или 1. Первые шесть координат легко находятся из уравнения решения которого имеют вид где Наконец, применим алгоритм Евклида к

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

Если то н. о. д. равен 1001110 1, если многочленов равен н. о. д. многочленов совпадает с Оба многочлена неприводимы над полем и разложение является полным:

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

В частности, многочлен является степенью неприводимого многочлена тогда и только тогда, когда нуль-пространство матрицы имеет размерность 1. В этом случае решениями сравнения являются только скаляры поля и нуль-пространство матрицы содержит единственный вектор вида Если размерность нуль-пространства

матрицы равна то оно имеет базис, состоящий из нормированных многочленов Без потери общности можно считать, что и что степени остальных многочленов положительны.

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

Пусть некоторая -матрица над где Тогда невырожденна, так как если для всех то ] для всех следовательно, что противоречит линейной независимости Так как в столбце матрицы стоят различные элементы, то, применяя к алгоритм Евклида, получим разложение на различные множители. Степени неприводимых многочленов выделяются тогда и только тогда, когда Так как невырожденна, то для каждых существует некоторое такое, что Следовательно, некоторый многочлен выделяет степени любых двух неприводимых делителей

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

Если достаточно велико, то к этому алгоритму может быть применено несколько остроумных приемов, некоторые из которых обсуждаются во втором томе книги Кнута [1968].