и выходных данных, что и в алгоритме Е. Он имеет то достоинство, что при поиске наибольших общих делителей коэффициентов требуется выполнять меньше вычислений.

С1. [Сведение к примитивным полиномам.] Как и на шаге Е1 алгоритма Е, установить d i- gcd(cont(u),cont(t;)) и заменить [u{x),v{x)) на (pp(u(a;)),pp(t;(a:))). Установить д i- h i- I.

C2. [Псевдоделение.] Установить S i- deg(M) - deg(t;). Вычислить r{x) с использованием алгоритма R. Если r{x) = О, перейти к шагу С4. Если deg(r) = О, заменить v{x) постоянным полиномом "1" и перейти к шагу С4.

СЗ. [Подгонка остатка.] Заменить полином и{х) на v{x) и t;(a;) на r{x)/gh. (В этот момент все коэффициенты г{х) кратны gh.) Затем установить д i{u), h h}-g и вернуться к шагу С2. (Новое значение h будет в области 5, даже если 6 > 1.)

С4. [Присоединение содержания.] Вернуть в качестве ответа d- pp(t;(a;)).

Если применить этот алгоритм к рассмотренным ранее полиномам (9), то получится такая последовательность результатов в начале шага С2.

и{х) v{x) д h

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

3,0,5,0,-4,-9,21 -15,0,3,0,-9 3 9 (15)

-15,0,3,0,-9 65,125,-245 -15 25

65,125,-245 -9326,12300 65 169

В конце алгоритма r{x)/gh = 260708.

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

Для анализа алгоритма С и доказательства его корректности рассмотрим полученную с его помощью последовательность полиномов ui{x), U2{x), из{х), где ui{x) = и{х) и U2{x) = v{x). Пусть Sj = Uj - для j > 1, где rij = deg(uj), и пусть gi=hi = 1, gj = i(uj), hj = h]zt-gf- для j > 2. Тогда

gp+ui{x) = U2{x)qi{x) + gih{U3{x), Пз < пг;

g=+U2(a;) = из{х)д2{х) + g2h2u4{x), гц < Пз; (16)

д1\з{х) = U4{x)q3{x) + дзН1щ{х), щ < гц

и т. д. Процесс прекращается, когда Пк+\ = deg{uk+i) < 0. Покажем, что полиномы Из (а:), Ui{x), ...имеют коэффициенты из S, а именно - что множитель gjhj делит все коэффициенты остатков. Кроме того, покажем, что все значения hj принадлежат S. Доказательство весьма запутанно, и его легче понять, рассмотрев конкретный пример.

Предположим, как и в (15), что щ = 8, пг = 6, пз = 4, П4 = 2, ns = 1, Пб = О, так что 5i = 62 = 6з = 2, 84=8 - 1. Запишем u\(x) = а&х +ax Л-----hao.

= м.

(17)

U2{x) = hx-irhx ----+ 60, ..., Ub{x) = eix + eo, uq{x) - /0, так что hi = I, = 6,

hi = cl/bl, /14 = dje/cl- Рассмотрим табл. 1 с учетом принятых обозначений. Для определенности будем считать, что коэффициенты полиномов целые. Имеем blui{x) = U2{x)qi{x) +из{х); так что, если умножить строку А5 на 6 и вычесть подходящие кратные строк Вт, Bq и Б5 (соответствующие коэффициентам qi{x)), можно получить строку С5. Если также умножить строку А4 на 6g и вычесть кратные строк Be, В5 и В4, можно получить строку С4. Аналогично получим clu2{x) = U3{x)q2{x) + 6б"4(х). Умножив же строку Вз на с, вычтя целые кратные строк Сь, С4 и Сз и разделив на Ь, получим строку D3.

Для доказательства того, что U4{x) имеет целые коэффициенты, рассмотрим матрицу

Аг /08 От Об 05 О4 О3 02 01 Оо О О \

Al О 08 07 Об 05 04 оз 02 Oi Оо о

Ао О О 08 О7 Об О5 О4 Оз 02 Oi Оо

В4 be 65 64 63 62 61 60 о о о о

Вз О 6б 65 64 63 62 61 Ьо О О О

В2 О О 6б 65 64 63 62 61 6о О О

Bi О О О 6б 65 64 63 62 61 Ьо О

Бо \ О О О О 6б 65 64 Ьз 62 61 Ьо I Указанные операции со строками и перестановки строк приводят к преобразованию матрицы М в

В 4 /6б 65 64 Ьз 62 61 6о О О О

Бз О 6б 65 64 63 62 61 6о О О

В2 О О 6б Ьь 64 63 62 61 Ьо О

Bi О О О 6б 65 64 63 62 61 Ьо О

Сг О О О О С4 Сз С2 ci Со О О

Ci О О О О О С4 Сз сг ci Со О

Со О О О О О О С4 Сз Сг ci Со

Do V О О О О О О О О d2 dl do / В соответствии с тем, каким образом была получена матрица М из М, имеем

bl-b\-bl.{z\lb\)-delMo = ±delMo,

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

/08 07 Об аь а4 Оз аг О \

О 08 О7 Об О5 О4 Оз Оо О О 08 07 Об 05 04 01

6б 65 64 Ьз 6г 61 Ьо О

О 6б 65 64 63 62 61 О

О О 6б 65 64 Ьз 6г О

О О О 6б 65 64 63 Ьо

V О О О О 6б 65 64 61 /

Поскольку 6бС4 ф О, это доказывает, что di -целое. Аналогично целыми являются 2 и do-

= М.

(18)

blicl/bD-det

•dl.

Таблица 1

КОЭФФИЦИЕНТЫ, ПОЯВЛЯЮЩИЕСЯ в АЛГОРИТМЕ С

В общем,так же можно показать, что Uj+i{x) имеет целые коэффициенты. Если начать с матрицы Л/, состоящей из строк с Л„2 „. по Ао и с Вщ-п, по Во, и выполнить указанные в табл. 1 операции над строками, можно получить матрицу М,

состоящую из расположенных в некотором порядке строк от B-nj по Bns-nj + l,

затем -от С„, „ по C„, „+i,..., от Р„. , „, по Pi, от Qm-i- по Qo и, наконец, Ro (строки, содержащей коэффициенты Uj+i{x)). Извлекая подходящие столбцы, покажем, что

(92*+VffЛ)"-"+(9з+V92Л)"-"+•••(sV9,-l*i-l)"-"+

xdetMo = ±92"""5з""---Э;1Г""9?"""г-„ (19)

где Г(-данный коэффициент Uj+i{x), а Мо - подматрица М. h выбираются очень хитрым способом (см. упр. 24) - так, чтобы это уравнение упростилось до

det Мо = ± г,.

(20)