8. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ

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

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

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