6.2.3. Разложение полиномов на множители разных степеней (частичное) над конечными полями

В этом разделе мы пользуемся теоремой 3.3.21, чтобы частично разложить на множители свободный от квадратов полином а именно мы воспользуемся тем, что неприводимый полином степени d делит но не делит для Поэтому мы можем выделить неприводимые множители каждой степени отдельно, добавив в алгоритм соотношения

и используя теорему 6.2.2.

DDF. Разложение на сомножители разных степеней (Distinct Degree Factorization)

Вход: — свободный от квадратов полином степени над

Выход: Полиномы над такие, что — произведение всех нормированных неприводимых сомножителей степени d полинома

1. [Инициализация]

2. [Конец?] {Отметим, что в этом месте все неприводимые сомножители полинома различны и их степени Если то выход [процедура заканчивается, поскольку либо либо — неприводимый полином], иначе

3. [Вычисление [Это — произведение всех неприводимых сомножителей полинома степени которых равны Если , то перейти к шагу 2. [Ниже мы обсуждаем, как получить сомножители, если степень полинома больше

Пример. Применяя DDF к (этот полином был разложен на множители в разд. 3.3.1), получаем следующее.

При первом проходе на шаге 1 мы имеем поскольку на шаге 2 мы имеем На шаге 3 мы получаем и обновляем заменяя их на соответственно.

При втором проходе на шаге 2 мы имеем на шаге 3 тогда и мы обновляем заменяя их на соответственно.

Последующие проходы шагов 2 и 3 не дают новых сомножителей, и, следовательно, мы получили всего три сомножителя, а именно сомножитель 12-й степени, являющийся произведением трех полиномов степени 4. (Заметим, что в мы имеем См. также историческое замечание 1.)

Мы видим, что в приведенном выше алгоритме требуется вычислять и

для Поэтому вычисление (частичного) разложения на множители различных степеней может быть выполнено за полиномиальных умножений по модулю Мы можем уменьшить число полиномиальных умножений по модулю следующим образом (Lenstra, 1982b).

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

Теорема 6.2.9. Для любого полинома рассматриваемого как вектор v своих коэффициентов,

Доказательство. Пусть где Тогда

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

Другой способ нахождения (частичного) разложения на сомножители разных степеней полинома предложен в работе (Berlekamp, 1970). Этот метод использует ядро матрицы , где I — единичная -матрица, и может быть расширен до полного разложения в Обсуждение этого метода не входит в данную книгу.

Мы видели, что алгоритм DDF определяет произведение всех неприводимых сомножителей каждой степени d, и поэтому он

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

Обозначим через число различных неприводимых сомножителей степени i полинома и пусть — ранг ядра для . Пусть есть -матрица, где

Интересный результат Смита (Smith, 1876) утверждает, что

где — функция Эйлера, а в 1956 г. Шварцом [см. также (Schwarz, 1939)] было показано, что

Поэтому матрица А обратима, и вектор однозначно определяется вектором и. Так например, если для данного полинома степени 8 мы получили то мы знаем, что у него два сомножителя степени 1 и два сомножителя степени 3. Дополнительные детали могут быть найдены в работе (Gunji, Arnon, 1981).

Расщепление сомножителей различных степеней.

Таким образом мы редуцировали проблему разложения на множители к задаче разделения произведений полиномов одной и той же степени. Чтобы получить метод полного разложения в нам нужно научиться расщеплять на неприводимые сомножители, когда Для этого имеется несколько способов. Мы изложим простой вероятностный алгоритм, предложенный Кантором и Цассенхаузом (Cantor, Zassenhaus, 1981), основанный на следующем тождестве. Если — произвольное нечетное простое число, то

для всех полиномов поскольку полином делится на все неприводимые полиномы степени d (см. лемму 6.2.10). Приведенное выше тождество основано на полиномиальном разложении, справедливом для нечетного :

Лемма 6.2.10. Пусть произведение двух или более различных неприводимых полиномов одной и той же степени d по модулю нечетного простого . Тогда для любого полинома случайно выбранного среди полиномов степени по модулю , полином будет собственным сомножителем полинома с вероятностью

которая не меньше, чем 4/9.

Локазательство. Каждый элемент поля является корнем полинома

Поэтому для элементов поля имеет место равенство для элементов — равенство и для одного элемента, — равенство

Из греко-китайской теоремы об остатках для полиномов (см. теорему 6.2.12) нам известно, что кольцо изоморфно прямой сумме экземпляров поля Если — элемент кольца X, то

имеет в качестве компонент только 0, 1, —1. Число таких что не имеет компонент, равных 1, равно

и, таким образом, число таких что имеет по крайней мере одну компоненту, равную 1, равно

Из них число таких что все компоненты равны 1, равно

Следовательно, число таких что имеет по крайней мере одну компоненту, равную 1, и по крайней мере одну компоненту, отличную от 1, равно

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

является собственным делителем полинома Это происходит с вероятностью

Так как (поскольку эта вероятность не меньше, чем

Видно, что при мы получаем

Чтобы вычислить мы сначала возведем в степень по модулю пользуясь бинарным алгоритмом возведения в степень Е, описанным в разд. 2.3.2, а затем вычтем 1.

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

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

Заметим также, что если — неприводимый полином степени d в — произвольный полином, то значение полинома является целым числом (т.е. полиномом степени 0). Чтобы в этом убедиться, положим Поскольку в поле полиномиальных остатков по модулю в этом поле имеет место равенство Поэтому является одним из корней уравнения а следовательно, — целое число.

Лемма 6.2.11. Пусть — произведение двух или более различных неприводимых полиномов одной и той же степени d по модулю 2. Тогда для любого полинома случайным образом выбранного среди полиномов степени по модулю 2, полином является собственным делителем полинома с вероятностью

Локазательство. Локазательство аналогично доказательству леммы 6.2.10 и остается в качестве упражнения.

Пример. Попробуем расщепить полином 12-й степени полученный в примере, следующем за алгоритмом DDF, который является произведением трех полиномов степени 4. Следуя лемме 6.2.11, выберем случайным образом полином степени вычислим его след а затем полином являющийся делителем полинома (повезло!). Теперь нам осталось разложить полином на два сомножителя степени 4; читателю остается закончить пример (и испытать таким образом свое счастье).

Заметим, что для любого имеет место разложение

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

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