5.1.2. Неклассический подход: модулярный алгоритм для наибольшего общего делителя

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

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

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

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

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

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

(1) Если полином неприводим над целыми по модулю , где не делит , то неприводим также над целыми числами; по существу это теорема 3.2.16.

(2) Если полиномы взаимно просты над целыми по модулю где не делит и не делит то полиномы взаимно просты над целыми числами; это следует непосредственно из теоремы 5.1.2.

М. Модулярный алгоритм (Modular Algorithm)

Вход: Два примитивных полинома от одной переменной с целыми коэффициентами.

Выход: Полином над целыми числами.

1. [Инициализация] Положить с Выбрать простое , которое не делит и вычислить нормированный полином Положить если , то вернуть

Положить ).

Если (где оба деления выполняются над целыми числами), то вернуть

3. [Новое простое] Выбрать новое простое число которое не делит и вычислить нормированный полином если то вернуть

4. [Несчастливое ] Если то — несчастливое простое число; перейти к шагу 3. Если то — несчастливое простое число; положить и перейти к шагу 2.

5. [Цикл по коэффициентам] В этой точке Положить выполнять: применить к коэффициентам при и по модулю пусть — результат интерполяции; положить [При использовании симметричной системы вычетов коэффициенты полинома по абсолютной величине заметим также, что полином нормирован.]

6. [Обновление] Положить и перейти к шагу 2.

Анализ времени работы, алгоритма М. Из теоремы 5.1.2 следует, что приведенный выше алгоритм завершается, поскольку число несчастливых простых чисел конечно. [См. также (Brown, 1971, th. 1), где дана оценка числа возможных несчастливых простых Браун показал, что преимущество модулярного алгоритма над классическими проявляется только тогда, когда данные полиномы достаточно большие и достаточно плотные. В разреженном случае (много отсутствующих членов) преимущество анализировать трудно.

Пример предложен чуть дальше. Предыдущий алгоритм не использует априорную оценку числа различных используемых

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

M1. Модулярный алгоритм, версия 1 (Modular Algorithm, Version 1)

Вход: Два примитивных полинома от одной переменной с целыми коэффициентами.

Выход: Полином над целыми числами.

1. [Инициализация] Выбрать простое , которое не делит и вычислить Положить если то вернуть Положить

2. [Новое простое] Выбрать новое простое число которое не делит Вычислить Если то вернуть

3. [Несчастливое простое?] Если то — несчастливое простое число; перейти к шагу 2. Если то — несчастливое Простое число; положить и перейти к шагу 2.

4. [Цикл по коэффициентам] В этой точке Положить Для выполнять: применить к коэффициентам при по модулю соответственно; пусть q — результат интерполяции, положить (Использовать симметричную систему вычетов.)

5. [Готово?] Положить Еслир то вернуть иначе перейти на шаг 2.

В действительности значение В, используемое в приведенном выше алгоритме, — это оценка максимума абсолютной величины коэффициентов полинома Такая оценка может быть получена из теоремы А.О. Гельфонда (Трансцендентные и алгебраические числа М.: Гостехиздат, 1952), но в практических вычислениях вместо этого используется максимум абсолютных величин коэффициентов полиномов Выбирается значение так как оно работает в большинстве случаев (Brown, 1971). Ясно, что существуют исключения; например, если то

и мы имеем дело со случаем, когда коэффициенты делителя больше коэффициентов делимого.

Заметим, что обе версии модулярного -алгоритма легко обобщить для обработки полиномов от многих переменных. Можно также воспользоваться алгоритмами подъема, описанными в гл. 6, чтобы найти наибольший общий делитель двух полиномов над . Это — так называемый расширенный -алгоритм Цассенхаузена [Extended Zassenhaus который не описывается здесь, но подробности можно найти в литературе (Miola et al., 1974; Moses et al., 1973; Yun, 1974).

Пример. Найдем наибольший общий делитель полиномов

Используя М, заметим сначала, что а затем для Затем, на шаге 2 вычисляем полином который делит как так и . Поэтому .

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