6.2.4. Алгоритм Берлекэмпа разложения на множители над конечными полями

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

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

Теорема 6.2.12 (греко-китайская теорема об остатках для полиномов). Пусть — полиномы из кольца причем взаимно прост с для всех . [Эквивалентно, мы можем взять в качестве различные неприводимые полиномы над этим полем], и пусть — произвольные полиномы в Тогда существует единственный полином такой, что

[т.е. полином определен по модулю и

Лругими словами, отображение, ставящее в соответствие каждому полиному из r-вектор , где является биекцией между

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

Отображение используемое в теореме 6.2.12, эквивалентно утверждению поскольку мы рассматриваем полиномиальную арифметику по модулю .

Теорема 6.2.12 утверждает, что для произвольного -вектора целых чисел по модулю существует единственный полином такой, что

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

Более того, справедлив следующий результат.

Теорема 6.2.13. В конечном поле имеет место разложение

Доказательство. Для любого элемента s по малой теореме Ферма мы имеем [равенство имеет место, поскольку вычисления производятся в значит, s является корнем полинома или, эквивалентно, является делителем полинома . Поскольку это верно для всех s произведение является делителем полинома Однако

а поскольку оба этих полинома нормированы,

Следствие 6.2.14. Для любого полинома над имеет место равенство

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

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

Тогда

Локазательство. По предположению

а следовательно, делит Поэтому

по следствию 6.2.14. Кроме того, дляв полиномы также взаимно просты. Поэтому (см. также упр. 1 к этому разделу).

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

Поэтому — формула полного разложения, и она является основной формулой, используемой в алгоритме Берлекэмпа.

Подведем итоги. Пусть — свободный от квадратов полином степени , который мы хотим разложить на множители над полем и предположим, что каким-то образом мы можем найти полиномы в кольце такие, что [Заметим, что если степень полинома то поскольку коэффициент при наивысшей степени не равен нулю.] Из теоремы 6.2.13 мы знаем, что у полинома в поле имеется корней, а именно ; следовательно, полином разлагается на множители по модулю следующим образом: Заменяя на получаем разложение

в кольце Так как полином делит то

Кроме того, поскольку полиномы — ей взаимно просты при мы имеем (по следствию 6.2.14, теореме 6.2.15 и упр. 1)

что является нетривиальным разложением на множители полинома над

Таким образом, основная задача состоит в определении полиномов Это делается путем решения системы линейных уравнений, и введенная в разд. 6.2.3 матрица Q оказывается очень полезной; в частности, очень важную роль играет нуль-пространство

(определенное ниже) матрицы , где I — единичная -матрица.

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

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

Деля на получаем

где [Заметим, что полиномы легко вычислить, если мы знаем

Теперь, заменяя соответствующими выражениями из получаем

Таким образом, делит тогда и только тогда, когда делит полином

степень которого . Поэтому полином степени n будет делить тогда и только тогда, когда последний равен нулю.

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

Пусть

— матрица, строки которой образуют коэффициенты полиномов-остатков (Замечание. Сначала выписываются коэффициенты меньших степеней х.) Тогда имеет место

Теорема 6.2.16. Полином решением сравнения тогда и только тогда, когда

Локазательство. Доказательство следует из того, что имеет место тогда и только тогда, когда

(См. также теорему 6.2.9.)

Пусть N — множество векторов таких, что , где t — вектор коэффициентов полинома -мерный нулевой вектор. Тогда N назьшается нуль-пространством матрицы Пусть — множество векторов в N, таких, что каждый вектор а из N является линейной комбинацией векторов [заметим, что для каждого вектора b имеется соответствующий полином , т.е. для любого вектора существуют числа такие, что Наименьшее , для которого существует такое множество , называется размерностью пространства N, а само множество называется базисом нуль-пространства. (См. также приложение.)

Таким образом, в силу теоремы 6.2.16 нахождение подходящих полиномов эквивалентно определению нуль-пространства матрицы (см. также историческое замечание 2). Как мы убедимся ниже, мы легко можем вычислить нуль-пространство и, следовательно, можем применить теорему 6.2.15 и вычислить сомножители полинома Однако как мы узнаем, что нашли полное разложение полинома Ответ дается следующей теоремой.

Теорема 6.2.17. Число различных неприводимых сомножителей равно размерности нуль-пространства матрицы

Доказательство. Полином делит тогда и только тогда, когда каждый полином делит

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

У этой системы имеется решений. Таким образом, размерность нуль-пространства матрицы равна и равна числу различных нормированных неприводимых сомножителей полинома , а ранг матрицы равен . (См. также упр. 2 к этому разделу.)

Кроме того, теорема 6.2.17 дает нам третий тест неприводимости (два первых теста см. в разд. 6.2.2).

Тест 3. Полином неприводим в тогда и только тогда, когда нуль-пространство матрицы одномерно и

Локазательство. По теореме 6.2.17 нуль-пространство матрицы одномерно тогда и только тогда, когда т.е. является степенью неприводимого полинома. Тогда неприводим в том и только том случае, когда

Теорема 6.2.18. Пусть — базис нуль-пространства матрицы Тогда для каждого , существуют такие, что делит, не делит

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

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

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

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

ВА. Алгоритм Берлекэмпа (Berlekamp’s Algorithm)

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

Выход: Неприводимые сомножители полинома над

1. [Построение матрицы Q] Построить -матрицу Q так, как описано в Как показано ниже, это можно сделать одним из двух способов в зависимости от того, насколько велико число .

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

3. [Вычисление сомножителей] Пусть — полином, соответствующий вектору Вычислим для всех . В результате по теореме 6.2.15 получим нетривиальное разложение полинома Если с использованием получено менее сомножителей, вычислим для всех s и всех сомножителей найденных к данному времени, для пока

не найдем сомножителей. Теорема 6.2.18 гарантирует, что таким образом мы найдем все сомножители полинома Если мало, то вычисления на данном шаге весьма эффективны. Однако для больших (например, р > 25) может быть предложен лучший способ, разбираемый ниже.

Анализ времени работы алгоритма ВА. Число вычислений, выполняемых на шаге 2 алгоритма Берлекэмпа, равно (Это было показано при доказательстве анализа времени вычислений алгоритма ASPRS в разд. 5.3.3.) Из разд. 3.2.2 нам известно, что мажорирует время вычисления поскольку требуется не более вычислений для каждого вектора b из базиса и не более из этих вычислений будут нетривиальны, получаем

Читателю следует отметить зависимость этого алгоритма от . Для больших алгоритм неэффективен. Кроме того, из следствия 6.1.2 нам известно, что среднее число сомножителей приблизительно равно

Пример. Разложим на множители над свободный от квадратов полином или эквивалентный ему нормированный полином (полученный домножением полинома ) на Это достаточно длинный пример, но читателю следует основательно его изучить.

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

На первом шаге алгоритма ВА вычисляется матрица Q, размер которой в этом случае равен Первая строка матрицы Q всегда имеет вид (1,0,0,0), представляя полином . Вторая строка представляет третья представляет и, наконец, последняя представляет . Очевидно, что нам нужно научиться быстро вычислять если известно ниже мы предлагаем такую процедуру общего вида.

Пусть и предположим, что

тогда

где

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

Таким образом, вторая строка Q равна (12,0,4,5). Аналогично мы определяем и, наконец,

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

то

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

Этим завершается шаг 1 алгоритма Берлекэмпа.

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

Алгоритм этих вычислений основан на наблюдении, что любой столбец матрицы М можно домножить на ненулевую величину и любое кратное одного из ее столбцов может быть прибавлено к другому столбцу без изменения ранга или векторов , что полиномы соответствующие базисным векторам - нуль-пространства матрицы суть все решения сравнения Таким образом, мы имеем следующий алгоритм приведения к треугольному виду (Knuth, 1981; Lidl et al., 1984).

NS. Алгоритм нуль-пространства (Null-Space algorithm)

Вход. Матрица размера элементы которой принадлежат полю.

Выход: Линейно независимые векторы , такие, что , где ранг матрицы М.

1. [Инициализация флагов столбцов] Положить

2. [Главный цикл] Для выполнять (если существует столбец j, такой, что то выполнять следующее [умножить столбец j матрицы М на — так что станет равным —1; затем прибавить умноженный на столбец j к столбцу i для всех -наконец, положить . Если не существует столбца j, такого, что , то положить и выдать вектор где для

Применяя описанную выше процедуру к вычисленной выше матрице элементы которой принадлежат полю мы приходим к следующему (следует помнить, что в алгоритме NS строки и столбцы матрицы нумеруются с 0, а не с 1).

При мы получаем на выходе вектор соответствующий полиному-константе 1. При мы можем взять j равным 0,1,2 или 3, поскольку для i = 0,1,2,3; выбор полностью произволен, хотя он влияет на получаемые на выходе векторы. Мы выбираем и, пользуясь таблицей обратных величин, вычисленной в начале этого примера, получаем операции над столбцами , описанные в приведенном выше алгоритме, меняют матрицу М на матрицу

Выделенный жирным шрифтом элемент 12 в строке 1 и столбце 0 означает, что . При мы можем выбрать и, действуя аналогичным образом [т.е. вычисляя сначала

, а затем полагая получим матрицу

Как и выше, выделенный жирным шрифтом элемент 12 в строке 2 и столбце 1 означает, что Теперь каждый столбец, не содержащий выделенного жирным шрифтом элемента, состоит полностью из нулей, поэтому при алгоритм дает на выходе вектор соответствующий полиному

Из вида матрицы при ясно, что векторы удовлетворяют уравнению Поскольку выполненные выше вычисления дали два линейно независимых вектора, полином должен иметь в точности два неприводимых сомножителя над которые получаются на шаге 3 алгоритма Берлекэмпа.

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

Проверка:

Ясно, что когда большое и мы хотим вычислить наибольшие общие делители для всех мы должны выполнить огромный объем работы. Кантор и Цассенхауз (Cantor, Zassenhaus, 1981) предложили лучший способ вычислений. Если — произвольное решение уравнения нечетно, то . Это предполагает, что мы будем вычислять

При этом с некоторой вероятностью является нетривиальным делителем полинома Для определения этой вероятности

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

[Заметим, что не может одновременно быть поскольку Равенство выполняется тогда и только тогда, когда что имеет место тогда и только тогда, когда [см. (В1)]. Мы знаем, что в точности целых чисел s в интервале удовлетворяют сравнению ). Если — выбранное случайным образом решение уравнения все решений которого равновероятны, то вероятность того, что совпадает с полиномом равна Те же самые рассуждения справедливы для и, таким образом, вероятность того, что нетривиальный делитель полинома будет получен путем вычисления (В 12), равна для всех .

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

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