полиномов, т. е. задачу поиска значения и{х) при данном а; € 5 с использованием минимально возможного числа операций. Частный случай вычисления х" при больших п достаточно важен и разбирается отдельно в разделе 4.6.3.

Первым большим набором компьютерных подпрограмм для работы с полиномиальной арифметикой стала система ALPAK [W. S. Brown, J. P. Hyde, and В. A. Tague, Bell System Tech. J. 42 (1963), 2081-2119; 43 (1964), 785-804, 1547-1562]. Другой ранней вехой в этой области стала РМ system Джорджа Коллинза (George Collins) [САСМ 9 (1966), 578-589; см. также С. L. Hamblin, Сотр. J. 10 (1967), 168-171].

УПРАЖНЕНИЯ

1. [10] При работе с полиномиальной арифметикой по модулю 10 чему будет равна разность 7х + 2 и х + 5? Чему будет равно произведение 6х -I- х -I- 3 и 5х -I- 2?

2. [17] Истинны ли следующие утверждения? (а) Произведение нормированных полиномов нормировано. (Ь) Произведение полиномов степени тип имеет степень т + п. (с) Сумма полиномов степени тип имеет степень max(;n,n).

3. [М20] Если каждый из коэффициентов Иг, . •., мо, fs, .. •, «о в (4) представляет собой целое число, удовлетворяющее ус;ювиям \щ\ < mi, \vj \ < тг, то чему равно максимальное абсолютное значение произведения коэффициентов Wk?

► 4. [21] Можно ли умножение полиномов по модулю 2 упростить с помощью обычных арифметических операций на двоичном компьютере, если коэффициенты упакованы в машинные слова?

► 5. [М21] Покажите, как можно умножить два полинома Степени < п по модулю 2 со временем умножения, пропорциональным 0(п*) при больших п, адаптируя метод Карацубы (см. раздел 4.3.3).

4.6.1. Деление полиномов

Разделить один полином на другой можно так же, как одно целое число с многократной точностью на другое, при вьшолнении арифметических операций с полиномами над полем. Поле 5 представляет собой коммутативное кольцо с единицей, в котором точное деление возможно так же, как и операции сложения, вычитания и умножения.. Как обычно, это означает, что для любых и,«€5ии0в5 всегда имеется элемент w, такой, что и = vw. Наиболее важными полями коэффициентов, появляющимися в приложениях, являются

a) рациональные числа (представленные в виде дробей; см. раздел 4.5.1);

b) действительные или комплексные числа (представленные в компьютере как приближения с плавающей точкой; см. раздел 4.2);

c) целые по модулю р, где р - простое число (деление может быть реализовано так, так предложено в упр. 4.5.2-16);

d) рациональные функции над полем, т. е. частное двух полиномов, коэффициенты которых находятся в этом поле, а знаменатель нормирован.

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

Если даны два полинома, и{х) и v{x), над полем и t;(a;) ф О, можно разделить и{х) HEiv{x) и получить полином-частное q{x) и полином-остаток г{х), удовлетворяющие условиям

и{х) = q{x) v(x) + r{x), deg(r) < deg(t;). (1)

Легко увидеть, что существует не более одной пары полиномов [q{x),r{x)), удовлетворяющих этим соотношениям; в самом деле, если условиям (1) при одних и тех же полиномах U(а:) iiv{x) удовлетворяют две пары-[qi(x),ri{x)) и (92(2;), гг(а;)), - то gi(a;)t;(a;)-f-ri(a;) = 92(а:)t;(a;)-f-гг(а;), т. е. {qi{x) -q2ix))v{x) = Г2{х)-ri{x). Теперь, если qi{x) - q2{x) ф О, имеем deg((gi - 92) • v) = deg(gi - 92) + deg(t;) > deg(t;) > deg(r2 - ri), T. e. получаем противоречие (так как из равенства (gi(a:) - q2{xv{x) = Т2{х) - ri{x) следует deg((gi - 92) • v) = deg(ri - Г2) - Прим. перев.). Значит, 91 (а;) - 92(2:) = О и ri(a;) = Г2(а;).

Чтобы определить q{x) и г(а:), можно использовать алгоритм 4.3.ID для деления чисел с многократной точностью, только без переносов.

Алгоритм D (Деление полиномов над полем). Даны полиномы

и(х) = UmX" -\-----h ЩХ + Uo, V(x) = VnX +----f ViX + Vq

над полем 5, где t;„70Hm>n>0. Алгоритм находит полиномы

q(x) = g„ „a:"-" -(-...-(- go, r(a;) = r„ ia;"- -b • • • -b tq над полем S, удовлетворяющие условиям (1).

Dl. [Итерация по к.] Выполнять шаг D2 для к = т - п, т - п - 1, ..., 0; затем прекратить выполнение алгоритма с (r„ i,..., гр) = (u„ i, ...,uq).

D2. [Цикл деления.] Установить сначала qk Un+k/fn, а затем - uj i- uj - qkVj-k для j - n + к - 1, n + к - 2, к. (Действие последней операции состоит в замещении и(х) на и(х) - qkxv(x), полином степени <п + к.)

Пример использования алгоритма D приводится ниже, в (5). Количество выполняемых арифметических операций, в сущности, пропорционально п(т - п + 1). Обратите внимание, что явное деление коэффициентов вьшолняется только в начале шага D2 и знаменателем всегда является v„. Таким образом, если v(x) - нормированный полином (с Vn.= 1), реальное деление не производитдя вовсе. Если умножение более предпочтительно, чем деление, имеет смысл предварительно вычислить значение 1/vn и на шаге D2 выполнить умножение на эту величину.

Зачастую остаток г(а:) из (1) будет записываться как и(х) modt;(a;).

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

i) uv ф О, если и и v - ненулевые элементы 5;

ii) каждый ненулевой элемент и е S либо обратим, либо имеет "единственное" представление в виде произведения простых pi, ..., pt.

u = pi...pt, t>l. (2)

Обратимый элемент в данном случае представляет собой элемент, который имеет обратную величину, а именно - элемент и, такой, что uv = I для некоторого v Е S. Простой элемент - это не являющийся обратимым элемент р, такой, что уравнение р = qr истинно только тогда, когда либо q, либо г представляет собой обратимый элемент. Представление (2) единственно в том смысле, что если рх.. .pt = qi - .qs, где все р и g просты, то s = t и имеется перестановка tti ... 7Г( множества {\,...,t}, такая, чтоРх = axq, ..., pt - atqt для некоторых обратимых ах, at- Другими словами, разложение на простые множители единственно с точностью до порядка множителей и до умножения на обратимые.

Любое поле представляет собой область единственного разложения на множители, в которой каждый ненулевой элемент обратим и в которой не существует простых элементов. Целые числа образуют область единственного разложения, в которой обратимые элементы--hi и -1, а простые - ±2, ±3, ±5, ±7, ±11 и т. д. Случай,

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

Одним из ключевых фактов, связанных с полиномами (см. упр. 10), является то, что полиномы над областью единственного разложения образуют область единственного разложения. Полином, который является простым в этой области, обычно называется неприводимым. Многократно используя теорему о единственности разложения, можно доказать, что полиномы от нескольких переменных над множеством целых чисел или над любым полем с любым числом переменных могут быть единственным образом разложены на неприводимые полиномы. Например, полином от трех переменных 90а; - 120ху -Ь ISxyz - 24xyz над целыми числами представляет собой произведение пяти неприводимых полиномов 2-3 х {Зх - 4у) • {5х + yz). Тот же полином над рациональными числами является произведением трех неприводимых полиномов (ба;) • (За; - Ау) {Ъх -Н yz). Это разложение может быть записано как а; • (90а; - 120j/) • (а; + \yz) и еще бесконечным числом способов, хотя разложение, по существу, единственно.

Как обычно, мы говорим, что и{х) кратен полиному v{x), а t;(a;) является делителем и{х), если и{х) - v{x)q{x) для некоторого полинома q{x). Если есть алгоритм, который определяет, является ли и кратным v для произвольных ненулевых элементов и и и некоторой области единственного разложения 5, и позволяет определить w, если и = и то алгоритм D дает метод для выяснения, является ли и{х) кратным v{x) для произвольных ненулевых полиномов и{х) и t;(a;) над 5. Если и{х) кратно v{x), легко увидеть, что u„+a должно быть кратно u„ при переходе к шагу D2; отсюда будет найдено частное u(a;)/t;(a;). Применяя это наблюдение рекурсивно, получим алгоритм, который отвечает на вопрос, является ли данный полином над 5 от любого числа переменных кратным другому полиному над 5, а также алгоритм, который будет находить частное, если таковое существует.

Множество элементов области единственного разложения называется взаимно простым, если нет простого элемента этой области единственного разложения, который делит все остальные элементы. Полином над областью единственного