8.5. МОДУЛЬНАЯ АРИФМЕТИКА ПОЛИНОМОВ И ВЫЧИСЛЕНИЕ ИХ ЗНАЧЕНИЙ

Результаты, аналогичные результатам для целых чисел, справедливы и для полиномов. Пусть полиномы и

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

По аналогии с леммой 8.1 можно показать, что соответствие взаимно однозначно, если полиномы попарно взаимно просты и степень полинома и меньше степени полинома т. е. Более того, алгоритм 8.4 для вычисления вычетов применим к полиномам, если в качестве взять полиномы, а не целые числа. Вместо (числа битов в каждом ) надо рассматривать наибольшую степень полиномов Разумеется, сложность измеряется числом арифметических, а не битовых операций. Тогда справедлива теорема, аналогичная теореме 8.9.

Теорема 8.10. Перенеся алгоритм 8.4 на полиномы, можно найти вычеты полинома относительно полиномов за время где верхняя граница степеней полиномов и степень полинома и меньше степени полинома

Доказательство. Аналогично теореме 8.9; оставим его в качестве упражнения.

Следствие 1. Для нахождения вычетов полинома и относительно полиномов требуется не более

времени, где верхняя граница степеней полиномов и степень полинома и меньше степени полинома

Пример 8.5. Рассмотрим четыре полиномиальных модуля

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

Затем вычисляем

В самом деле,

Далее,

Заметим, что алгоритм БПФ из разд. 7.2 в действительности является реализацией этого алгоритма, когда в качестве берутся Алгоритм БПФ извлекает выгоду из выбора в качестве полинома Благодаря подходящему упорядочению множества полиномов каждое произведение равно разности степени х и степени и потому деление выполняется особенно легко.

Как было отмечено в разд. 7.2, если полином первой степени то и Поэтому случай, когда все полиномы имеют степень 1, особенно важен. Из теоремы 8.10 вытекает следующий результат.

Следствие 2. Значения полинома степени в точках можно вычислить за время О а

Доказательство. Чтобы вычислить точках вычисляем для Это занимает время в силу следствия 1, ибо здесь