6.2. Разложение на множители полиномов над конечным полем

Как мы уже видели в предыдущем разделе, разложение полиномов в , где — простое число, интересно не только само по себе, но также в связи с тем, что оно полезно при разложении на множители в (Читателю следует заглянуть здесь в разд. 3.3.) Любой полином степени мажет быть разложен на множители за конечное число шагов, поскольку существует возможных полиномов степени и мы можем просто проверить каждый из них, используя PDF. Однако этот метод проб и ошибок очень неэффективен.

В этом разделе мы подробно обсуждаем эффективный алгоритм Берлекэмпа разложения на множители в для малых простых р. Этот метод был найден в 1967 г. (Berlekamp, 1967,

1968) и переводит задачу разложения на множители в задачу решения системы линейных уравнений с коэффициентами в и нахождения наибольших общих делителей; последние две задачи могут быть решены очень эффективно; таким образом, это преобразование весьма желательно. (Берлекэмп в 1970 г. разработал также другой алгоритм для разложения на множители полиномов в при больших простых р; этот вопрос кратко обсуждается в разд. 6.2.4.)

Начнем с рассмотрения близкого материала.

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

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

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

Теорема 6.2.1. Пусть J — область с однозначным разложением. на множители произвольной характеристики и — не являющийся константой примитивный полином над J. Пусть — однозначное разложение на неприводимые множители, и пусть если в противном случае пусть [Условие имеет место тогда и только тогда, когда или характеристика области J делит ] Тогда

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

Предположим теперь, что характеристика области J равна , и пусть . Пусть и для положим

и

Тогда

и по теореме 6.2.1 мы имеем причем следует отметить, что кроме того, из теоремы 6.2.1 следует, что

а потому

Легко проверить, что алгоритм PSQFF, примененный к даст разложение и при условии, что он даст на выходе ; мы должны также дописать в конце шага 1 «если , то чтобы учесть случай Если , то мы получили разложение на свободные от квадратов множители. Однако если то для получения полного разложения на свободные от квадратов множители требуются дополнительные вычисления. Хотя совсем не очевидно, как это можно сделать для полиномов над произвольной областью J характеристики (не прибегая к алгоритму полного разложения), мы приводим алгоритм для частного случал, когда J — область полиномов от одной переменной над конечным полем. (В этом месте читателю следует еще раз посмотреть теоремы )

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

Теорема 6.2.2. Пусть — полином в кольце Тогда

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

поскольку все биномиальные коэффициенты делятся на . Более того, по малой теореме Ферма для любого целого числа с. Поэтому если

то мы получаем

Теорема 6.2.3. Пусть — полином в . Тогда в том и только том случае, когда есть степень некоторого полинома

Локазательство. Если , то . Обратно, если то может быть записан в виде . Пусть тогда лежит в

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

PSQFFF. Разложение полиномов на свободные от квадратов множители над конечным полем (Polynomial Square-free Factorization over a Finite Field)

Вход: — не являющийся константой нормированный полином в — простое число.

Выход: , такие, что разложение на свободные от квадратов множители.

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

2. [Основной цикл] если , то перейти к шагу 7.

3. [Итерация] если , то

4. [Вычисление

5. [Итерация] Если , то перейтп к шагу 3}.

6. [Конец?] Если , то выход из цикла (а также из алгоритма).

7. перейти к шагу 2.

Время вычислений этого алгоритма проанализировано в разд. 3.2.4, где приводится также пример. Во все время выполнения алгоритма PSQFFF выполняется соотношение и когда мы попадаем на шаг 6, значение — это наибольший индекс i, такой, что не делит имеет не являющийся константой делитель порядка i. Мы предполагаем также, что полиномы вычисленные на шагах 2 и 4 соответственно, нормированы.

На шаг 7 мы попадаем, только если поэтому в силу теоремы мы знаем вид полинома и легко вычисляем пользуясь тождеством