и если мы работаем над полем рациональных чисел, то единственными делителями £fm-n+i будут знаменатели q{x) и г{х). Это наблюдение приводит к мысли, что всегда можно найти полиномы q{x) и г{х), такие, что

e{vr-+u{x) = q{x)v{x) + r{x), deg(r) < n, (8)

где тп = deg(u) и n = deg(t;), для любых полиномов и{х) и v{x) ф О при условии, что m > п.

Алгоритм R {Псевдоделение полиномов). Даны полиномы

и{х) = Umx" Н-----h uix + Mo, t;(a;) = t;„a:" +----\-vix + vo,

где УпфОит>п>0. Этот алгоритм находит полиномы q{x) = gm-na:"~"H-----f-go

и r{x) = r„..ia;""" Н-----h го, удовлетворяющие (8).

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

R2. [Цикл умножения.] Установить сначала qk u„j.t;, а затем - Uj VnUj -Un+kVj-k для j = п+к-1, п+к-2,..., 0. (При j < к это означает, что Uj t;„Uj, поскольку мы рассматриваем t; i, v-2, •• как нули. Этих умножений можно избежать, если начать алгоритм с замены щ на t;~"~uf для О <t <т-п.)

Пример вычислений приведен ниже, в (10). Правильность алгоритма R легко доказать индукцией по m - п, поскольку при каждом вьшолнении шага R2, по сути, и{х) заменяется на i{y)u{x) - £{u)xv{x), где к = deg(u) - deg(t;). Заметьте, что в алгоритме не использовано деление; коэффициенты q{x) и г{х) сами по себе представляют некоторые полиномиальные функции от коэффициентов и{х) и v{x). Если Vn = 1, то алгоритм идентичен алгоритму D. Если и{х) и v{x)-полиномы над областью единственного разложения, можно, как и ранее, доказать, что полиномы q{x) и г{х) -единственны, поэтому другой способ псевдоделения над областью единственного разложения состоит в умножении и{х) на t;"""+ и применении алгоритма D, если известно, что все частные на шаге D2 будут существовать.

Алгоритм R может быть расширен до "обобщенного алгоритма Евклида" для примитивных полиномов над областью единственного разложения следующим образом. Пусть и(х) и v{x) - примитивные полиномы с deg(u) > deg(t;). Определим при помощи алгоритма R полином г{х), удовлетворяющий (8). Теперь можно доказать, что gcd(m(a:),t;(a;)) = gcd(t;(a;),r(a;)): любой общий делитель и{х) и v{x) делит v{x) и г(х); и обратно, любой общий делитель t;(a;) и г{х) делит £{v)~"u{x) и должен быть примитивным (поскольку примитивен v{x)), так что он делит и{х). Если г{х) = О, имеем gcd(u(a:),t;(a:)) = t;(a;); с другой стороны, если г{х) ф О, из-за примитивности t;(a;) имеем gcd(t;(a;),г(а;)) = gcd(t;(a:),рр(г(а:))), так что процесс может быть итерирован.

Алгоритм Е (Обобщенный алгоритм Евклида). Даны ненулевые полиномы и{х) и v{x) над областью единственного разложения S. Алгоритм вычисляет наибольший общий делитель и{х) и v{x). Предполагается существование вспомогательных алгоритмов для вычисления наибольшего общего делителя элементов 5, а также для деления а на 6 в 5 при 6 О и а, кратном Ь.

El. [Сведение к примитивным полиномам.] Установить d +- gcd(cont(w), cont(u)), используя вспомогательный алгоритм для вычисления наибольшего общего делителя в S. (По определению cont(u) представляет собой наибольший общий делитель коэффициентов и{х).) Заменить и{х) полиномом u(a;)/cont(u) = рр(и(а:)); точно так же заменить v{x) на pp(t;(a:)).

Е2. [Псевдоделение.] Вычислить г{х) с использованием алгоритма R. (Нет необходимости вычислять полином-частное д{х).) Если г{х) = О, перейти к шагу Е4. Если deg(r) = О, заменить v{x) постоянным полиномом "1" и перейти к шагу Е4.

ЕЗ. [Сделать остаток примитивным.] Заменить и{х) на v{x) и заменить v{x) на рр(г(а:)). Вернуться к шагу Е2. (Это-"евклидов шаг" аналогичный другим рассмотренным нами алгоритмам Евклида.)

Е4. [Присоединение содержания.] Алгоритм завершается, выдав ответ d v{x).

В качестве примера работы алгоритма Е вычислим gcd полиномов

и{х) = х + х- Зх" - Зх +8х + 2х-5,

v{x)=3x+ 5х-Ах-9х + 21

над целыми. Эти полиномы примитивны, так что на шаге El устанавливается d+- 1. На шаге Е2 выполняем псевдоделение.

(10)

-15 0 3 0 -9

Здесь частное q{x) равно 1 • За: + О • За: -f- -6 • З". Имеем

27и{х) = v(x)(9x - 6) + (-15ГГ + Зх - 9). (11)

Теперь шаг ЕЗ замещает и{х) на v{x) и v(x) на рр(г(а:)) = 5а:* - а; -f- 3. Дальнейшие вычисления приведены в следующей таблице, в которой показаны только коэффициенты.

и{х) v{x) г{х)

1,0,1,0,-3,-3,8,2,-5 3,0,5,0,-4,-9,21 -15,0,3,0,-9

3,0,5,0,-4,-9,21 5,0,-1,0,3 -585,-1125,2205 (12)

5,0,-1,0,3 13,25,-49 -233150,307500

13,25,-49 4663,-6150 143193869

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

алгоритма Евклида для полиномов над полем, описанного ранее в этом разделе. Получается неожиданно сложная последовательность.

и{х) v{x)

1, 0,1, О, -3, -3, 8,2, -5 3, О, 5, О, -4, -9, 21

3,0,5,0,-4,-9,21 ,o,i,0,-i

5 п i П -i -Ш -Q Ж

g, и, д, и, 3 25 25

117 п 441 233150 102500

25 25 19773 6591 233150 102500 1288744821

19773 6591 543589225

Для улучшения этого алгоритма можно свести и{х) и v{x) к нормированным полиномам на каждом шаге, чтобы удалить обратимые множители, слишком усложняющие коэффициенты. В действительности получится алгоритм Е над рациональными числами:

и{х) v{x)

1,0,1,0, -3, -3, 8, 2, -5 1,0,1,0, -, -3, 7 1 Г) i п 1 ч 7 in i о -

3,VJ, 3, о, ( 5)", 5

1 О -i О 2. 1 25 49 V;

5 5 13 13

1 25 49 1 6150

13 13 4663

1 -6150 1

4663

И В (13), И В (14) последовательность полиномов, полученная при помощи алгоритма Е над целыми числами, по сути, та же, что и в (12). Единственное отличие состоит в том, что полиномы умножаются на некоторые рациональные числа. Каким бы ни был полином, будь то 5x - х + 3, + х - или х* - \х + ,

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

Поучительно сравнить (12), (13) и (14) с (6), где мы определяли gcd тех же полиномов и{х) и v{x) по модулю 13 со значительно меньшими усилиями. Поскольку i{u) и t{v) не кратны 13, того факта, что gcd(u(a;), v{x)) = 1 mod 13, достаточно для доказательства, что и{х) и v{x) взаимно просты над кольцом целых (и, следовательно, над полем рациональных чисел). Мы вернемся к этому сохраняющему время наблюдению в конце раздела 4.6.2.

Алгоритм Коллинза. Остроумный алгоритм, в целом превосходящий алгоритм Е и, кроме того, предоставляющий информацию о поведении алгоритма Е, был разработан Джорджем Э. Коллинзом (George Е. Collins) [JACM 14 (1967), 128-142] и впоследствии улучшен В. С. Брауном (W. S. Brown) и Дж. Ф. Траубом (J. F. Traub) [JACM 18 (1971), 505-514; см. также W. S. Brown, ACM Trans. Math. Software 4 (1978), 237-249]. Он позволяет избежать вычислений примитивных частей на шаге ЕЗ, вместо чего производится деление на элемент 5, о котором известно, что он является множителем г{х).

Алгоритм С (Поиск наибольшего общего делителя над областью единственного разложения). В этом алгоритме используются те же предположения о входных