6.3.1. Линейный и квадратичный подъем

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

Пусть — полином степени в такой, что Кроме того, пусть — полиномы в

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

Алгоритм 6.3.1 (расширенный алгоритм Евклида в ). Для данных этот алгоритм вычисляет единственные (с точностью до обратимых множителей) полиномы такие, что над при условии, что Описание этого алгоритма уже было представлено в разд. 3.2.2 (ХЕА-Р).

Алгоритм 6.3.2 (решение полиномиального уравнения в ). Для данных полиномов таких, что над и старшие коэффициенты полиномов обратимы в этот алгоритм вычисляет полиномы такие, что над при условии, что следующим образом.

1. Хотя коэффициенты полиномов принадлежат не полю, а кольцу предположение об обратимости старших коэффициентов позволяет использовать PDF, алгоритм деления полиномов над полем, чтобы вычислить в полиномы такие, что

2. Полагаем

Тогда

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

Лемма 6.3.4 (Гензель). Пусть — полином степени в такой, что — простое число. Пусть — полиномы в такие, что над над Тогда в существуют единственные полиномы такие, что над над

Доказательство. Пользуясь алгоритмом 6.3.1, найдем полиномы такие, что Лостаточно показать, как построить для такие, что над над Предположим, что такие существуют для некоторого j 1, и пусть — такой полином в что над Пользуясь алгоритмом 6.3.2, вычислим такие, что над Определим

где следует отметить, что Очевидно, что — полиномы в над и

Очевидно, что доказанная выше лемма дает нам пошаговый метод подъема разложения, т.е. от Поэтому он называется алгоритмом линейного подъема. Заметим, что на практике часто требуется поднимать более двух сомножителей. В этом случае подъем осуществляется повторным применением леммы 6.3.4 к парам сомножителей, один из которых — полином а другой — произведение . А именно, если

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

Читателю следует тщательно изучить два следующих примера; в первом мы используем множество неотрицательных вычетов целых чисел, а во втором — симметричное множество вычетов.

HLLA. Алгоритм линейного подъема Гензеля (Hensel Linear-Lifting Algorithm)

Вход: Простое число , натуральное число к, а также полиномы оба такие, что

Выход: Полиномы оба такие, что а также ).

1. [Инициализация] Положить а затем применить расширенный алгоритм Евклида в (алгоритм 6.3.1, описанный в этом разделе) к полиномам и вычислить полиномы оба такие, что над

2. [Основной цикл] Для выполнять поправку ); затем применить алгоритм 6.3.2 (также описанный в этом разделе) к все чтобы вычислить полиномы такие, что над и положить

3. [Выход] Вернуть

Пример [линейная гензелева конструкция; не обязательно нормирован]. Рассмотрим полином для которого имеет место сравнение

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

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

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

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

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

Прежде чем мы перейдем ко второму алгоритму подъема, целесообразно сейчас просмотреть различные рассуждения, используемые при попытке разложить на множители полином над целыми числами (см. также разд. 6.1.2).

Прежде всего нам нужно убедиться, что над целыми числами свободен от квадратов, т.е. мы должны вычислить , где Величина используемых коэффициентов нам известна, так что мы используем один из модулярных -алгоритмов, описанных в разд. 5.1.2, т.е. мы должны вычислить над различными полями таковы, что где В — максимальный по абсолютной величине коэффициент полиномов а именно, мы попытаемся вычислить для [Напомним, что

В этом случае

Это число не разрешается, поскольку

. В этом случае

Поскольку степень последнего меньше степени полинома мы приходим к выводу, что 5 — несчастливое простое число; кроме того, мы заключаем, что нам не нужно испытывать еще какие-либо простые числа, поскольку свободен от квадратов над целыми числами. (Это также легко проверить, используя PSQFF.)

Убедившись, что полином свободен от квадратов, мы должны затем выбрать соответствующее простое число для того, чтобы применить алгоритм Берлекэмпа. Простое число должно быть таким, чтобы полином оставался свободным от квадратов и имел ту же степень, что и . Сделаем следующие замечания.

Это простое число использовать нельзя, поскольку

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

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

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

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

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

Ниже мы представим второй пример подъема разложения по до разложения по для некоторого j, пользуясь линейной конструкцией Гензеля; теперь используется симметрическая система вычетов

Пример [линейная конструкция Гензеля; — нормированный полином]. Рассмотрим полином При мы имеем

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

Пользуясь алгоритмом 6.3.1, получаем полиномы такие, что

в Затем из соотношения рассматриваются в кольце получаем

откуда

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

такие, что над а затем определим

Теперь легко проверить, что кроме того, заметим, что и в дополнение к этому (поскольку мы знаем окончательный ответ) [в действительности мы уже имеем ]

Мы имеем теперь для второй итерации новый полином

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

а это и есть искомые полиномы.

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

очевидно, означающие, что .

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

Лемма 6.3.5 (Zassenhaus, 1969). Пусть — полином в такой, что и пусть где для существуют полиномы такие, что над Тогда мы мажем определить полиномы такие, что над и

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

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

Детали реализации алгоритма квадратичного подъема могут быть найдены в литературе. Продемонстрировано, что квадратичный алгоритм подъема существенно быстрее линейного [см. работы (Lenstra, 1982b, p. 184-185; Miola et al., 1974; Yun, 1974; Zassenhaus, 1978)].