представляет собой строку W = а;*"" так что этот алгоритм включает в себя как частный случай алгоритм поиска gcd целых чисел.)

► 18. [М24] (Алгоритм Евклида для строковых полиномов.) Пусть Vi и V2-строковые полиномы, не равные одновременно нулю и имеющие общее левое кратное (это означает, что существуют не равные одновременно нулю строковые полиномы Ui и [/2, такие, что Ui Vl = U2V2). Назначение данного упражнения-найти алгоритм для вычисления их наибольшего общего правого делителя Н0ПД(У1,У2) и наименьшего общего левого кратного HOJlK(Vi, V2). Эти величины определяются следующим образом: Н0ПД(У1, V2) является общим правым делителем Vi и V2 (т. е. Vi = ТУ1Н0ПД(У1, V2) и V2 = TV2H0nfl(Vi, Vb) для некоторых Wi и TV2), и любой общий правый делитель Vi и V2 является правым делителем Н0ПД(У1, V2); HOJIK(Vi, V2) = ZiVi = Z2V2 для некоторых Zi и Z2, и любое общее левое кратное Vi и V2 является левым кратным для HOJIK(Vi, Vb).

Например, пусть Ui = аЬЪЪаЬ + abbab - bbab + ab - 1, Vi = babab + abab + ab - b; U2 = abb + ab - b, V2 = babbabab + bababab -f babab -f abab - babb - 1. Тогда имеем UiVi = t/2 Vb = abbbabbabab + abbabbabab + abbbababab + abbababab - bbabbabab + abbbabab - bbababab + 2abbabab - abbbabb+ababab - abbabb - bbabab - babab+bbabb - abb-ab+b. Для этих строковых полиномов можно показать, что Н0ПД(У1, V2) = аЫ-1 и HOJIK(Vi, V2) = UiVi.

Алгоритм деления из упр. 17 можно сформулировать так: если Vi и V2 являются строковыми полиномами, причем V2 О, и если Ui ф О и U2 удовлетворяет соотношению UiVi = U2V2, то существуют строковые полиномы Q и R, такие, что

Vi = QV2 + R, где deg{R) < degiVi).

Отсюда легко вывести, что Q и R определяются однозначно; они не зависят от данных Ui и U2. Кроме того, результат обладает право-левой симметрией в том смысле, что

U2 = UiQ + R, где deg{R) = deg(t/i) - deg(V2) + deg{R) < deg(t/i).

Покажите, что этот алгоритм для деления может быть расширен до алгоритма, вычисляющего HOJIK(Vi, V2) иН0ПД(У1, V2); фактически расширенный алгоритм находит строковые полиномы Zi и Z2, такие, что Z1V1+Z2V2 = Н0ПД(У1, V2). [Указание. Используйте вспомогательные переменные щ, иг, «п, V2, wi, гиг, U}i, w2, zi, гг, z[ и Sj, значения которых представляют собой строковые переменные; начните с установки «i <- Ui, иг <- t/г, <- Vi, t)2 <- V2 и на протяжении алгоритма поддерживайте выпатнение условий

Uiwi+U2UJ2 = щ, ziVi + Z2V2 = VI,

UlUli + U2U)2 = U2, zlVl + Z2V2 = V2,

uizi - U2zi = (-l)"t/i, wivi - wiV2 = (-l)"Vi,

-UIZ2 + U2Z2 = (-l)"t/2, -W2Vl -b W2V2 = (-1)"V2

на П-Й итерации. Это можно рассматривать, как "окончательное" расширение алгоритма Евклида.]

19. [М39] (Общие делители квадратных матриц.) В упр. 18 показано, что концепция наибольших общих правых делителей может иметь смысл при некоммутативном умножении. Докажите, что любые две целочисленные матрицы А и В размера п х п имеют наибольший общий правый матричный делитель D. [Предложение. Разработайте алгоритм, на вход которого поступают матрицы А и В, а на выходе получаются целочисленные матрицы JD, Р, Q, X, Y, где А = PD, В = QD и D = ХА + YB.] Найдите наибольший общий правый делитель матриц (3 ) и ( f).

20. [М40] Исследуйте точность алгоритма Евклида: что можно сказать о вычислении наибольшего общего делителя полиномов с коэффициентами, представляющими числа с плавающей точкой?

21. [М25] Докажите, что время вычисления, требуемое алгоритмом С для поиска gcd двух полиномов п-й степени над кольцом целых чисел, составляет 0(n(logiVn)), если коэффициенты полинома ограничены по абсолютному значению величиной N.

22. [М23] Докажите теорему Штурма. [Указание. Некоторые последовательности знаков невозможны.]

23. [М22] Докажите, что если и{х) в (29) имеет deg(u) действительных корней, то

deg(uj+i) = deg(uj) - 1 для О < j < к.

24. [М21] Покажите, что (19) упрощается до (20) и (23) упрощается до (24).

25. [М24] (В. С. Браун (W. S. Brown).) Докажите, что все полиномы Uj{x) в (16) для j >3 кратны gcd{l{u),£{v)), и поясните, как в соответствии с этим можно улучшить алгоритм С.

► 26. [М2б] Назначение этого упражнения - найти аналог для полиномов того факта, что цепная дробь с целыми положительными элементами дает наилучшее приближение действительных чисел (упр. 4.5.3-42).

Пусть и{х) и v{x) - полиномы над полем с deg(u) > deg(t)) и пусть ai{x), а2{х), ...- частные полиномы, образующиеся в результате применения алгоритма Евклида к и{х) и v{x). Например, последовательность частных в (5) и (6) представляет собой 9x + 7, 5ж -1-5, 6ж--5ж-Ь6ж-Ь5, 9а;-Ы2. Необходимо показать, что представления рп(ж)/?„(а;) цепной дроби IJai{x),a2{x),... II являются "наилучшими приближениями" малых степеней рациональной функции v{x)lu{x), где рп(ж) =A„-i(a2(x),... ,а„(ж)) и qn{x) = Kn{ai{x),... ,а„(ж)) - континуанты из 4.5.3-(4). По определению ро(ж) = g-i(x) = О, p-i(x) = qo{x) - 1.

Докажите, что если р(ж) и q{x) являются полино.мами, такими, что deg(g) < deg(g„) и deg{pu-qv) < deg(pn-iu-gn-it)) для некоторого n > 1, тор(ж) = cp„-i{x) и д(ж) = cqn-i{x) для некоторой константы с. В частности, каждый qn(x) является полиномом, "разбивающим запись" (record-breaking) в том смысле, что не существует ненулевого полинома q{x) меньшей степени, такого, что для любого полинома р(ж) полином р{х)и{х) -q{x)v{x) имел столь же малую степень, что и рп{х)и{х) - qn{x)v(x).

27. [М23] Предложите путь ускорения деления и{х) на v{x), если заранее известно, что остаток будет нулевы.м.

*4.6.2. Разложение полиномов на множители

Рассмотрим теперь задачу не только поиска наибольшего общего делителя двух или более полиномов, но и разложения полиномов.

Разложение по модулю р. Как и в случае целых чисел (разделы 4.5.2 и 4.5.4), задача разложения представляется существенно сложнее поиска наибольшего общего делителя. Однако разложение полиномов по модулю некоторого простого целого числа р не настолько сложно, как кажется. Гораздо проще найти множители произвольного полинома степени п по модулю 2, чем использовать любой известный метод для поиска множителей произвольного п-битового двоичного числа. Эта неожиданная ситуация является следствием поучительного алгоритма разложения, открытого в 1967 году Элвином Р. Берлекампом (Elwyn R. Berlekamp) [Bell System Technical J. 46 (1967), 1853-1859].

Пусть p-простое число; все арифметические операции над полиномами в приведенном далее материале выполняются по модулю р. Предположим, задан полином и{х), коэффициенты которого выбраны из множества {0,1, ...,р - 1}. Мы

можем считать, что и{х) нормирован. Наша цель - выразить и{х) в виде

и{х)=рг{хГ...рг{хГ, (1)

где pi{x), ..., рт{х) - различные нормированные неприводимые полиномы.

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

и{х) = «„ж" -ь • • -ь ыо = v{xfw{x), (2)

то производная (найденная так, как обычно, но по модулю р) будет равна

и{х) = nunx" -\-----h «1 = 2v(x)v{x)w{x) + v{x)w{x), (3)

а это выражение кратно v{x). Значит, наш первый шаг в разложении и{х) должен состоять в поиске

gcd{u{x),uix)) dix). (4)

Если d{x) равно 1, то, как мы только что убедились, и{х) свободен от квадратов, т. е. представляет собой произведение различных простых pi{x).. .рг{х). Если d{x) не равно 1 и d{x) ф и{х), то d(x) является собственным множителем и{х); соотношение между множителями d{x) и множителями u{x)/d{x) ускоряет процесс разложения для этого случая (см. упр. 34 и 36). И наконец, если d{x) = и{х), то необходимо, чтобы и(х) = 0; следовательно, коэффициент Uk при ж* ненулевой только тогда, когда к кратно р. Это означает, что и{х) может быть записан как полином вида v(x). В таком случае имеем

и(х) = у{х>)=Ых)). (5)

Процесс разложения может быть завершен нахождением неприводимых множителей v{x) и возведением их в степень р.

Тождество (5) может показаться читателю несколько странным, однако это важный факт, лежащий в основе алгоритма Берлекампа и других методов, которые мы обсудим чуть позже. Его можно доказать следующим образом. Если vi{x) и V2 (х) - некоторые полиномы по модулю р, то

Ых)+У2{х)У = Viix)P + {P)viix)P-V2ix) + ---+{/ ,)viix)v2ixy- +У2{хУ

= vi {xy+V2{x),

поскольку биномиальные коэффициенты (j), (pi) кратны р. Далее, если а - произвольное целое число, имеем а = а (по модулю р) согласно теореме Ферма. Таким образом, когда v{x) = VmX™ + Vm-ix™~ -\-----h to, находим, что

+ Vm-lX"- + + Vo = vixP).

Эти замечания показывают, что задача разложения сводится к задаче разложения свободных от квадратов полиномов. Таким образом, положим, что

и{х) =:pi{x)p2ix)...prix) (6)

является произведением различных простых сомножителей. К какой хитрости следует прибегнуть, чтобы суметь найти Pj{x), если дан только и{х)? Идея Берлекампа