Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 21
Текст из файла (страница 21)
Тогда сопФ(и) = -13, рр(и(х)) = 2хз — 3, сопг(и) = +7, рр(и(х)) = Зх+ 2, сопс(и и) = -91, рр(и(х) и(х)) = бхз+4хз — 9х — 6. Наибольшие общие делители. В случае единственного разложения можно го- ворить о наибольше.и общем делителе двух элементов; это общий делитель, кото- рый делится на наибольшее количество простых элементов (см.
формулу 4.5.2-(б)) . Однако, поскольку область единственного разложения может иметь много обрати- мых элементов, в определении наибольшего общего делителя присутствует некото- рая неоднозначность. Если ш — наиболыпнй общий делитель и и и, то а ° ш, где а — обратимый элемент, тоже является наибольшим общим делителем.
И обратно, предположение о единственности Разложения на множители влечет за собой вывод о том, что если и шм и шз представляют собой наибольшие общие делители и и и, то ю~ = а ° юз, где а — некоторый обратимый элемент. Другими словами, не имеет смысла говорить о конкретном наибольшем общем делителе (в оригинале— 'йо зрея)г оГ йе йгеагевг сопппоп Ж лгог" . — Прим.
нерее,) и и и. Существует целое множество наибольших общих делителей, ввждый из которых отличается от других на обратимый множитель. Рассмотрим теперь задачу поиска наибольшего общего делителя двух данных полиномов иад алгебраической системой Б, первоначально поставленную Пабло Ну- ньесом (РаЫо Хшж) в работе ИЬго де А)яеЬга (Апсзгегр, 1567). Если з — поле, то проблема относительно проста; наш алгоритм деления, алгоритм П, может быть расширен до алгоритма вычисления наибольшего общего делителя так же, как ал- горитм Евклида (алгоритм 4.5.2А), находящий наибольший общий делитель двух целых чисел, получается на основе алгоритма деления целых чисел: если и(х) = О, то йса(и(х),и(х)) = и(х); в противном случае йса(и(х),и(х)) = йсй(и(х),г(х)), где г(х) определяется (1).
Эта процедура называется алгоритмом Евклида для полиномов над полем. Впервые она бьиа использована Симоном Стевнном (Яшоп Взещп) в ГАгййшейдие (1еЫеп, 1585); см. А. Жгагб, Тез (Бпггез Магйешас(9пез де Яушоп Бгегш 1 (1.еЫеп, 1634), 56. Например, необходимо найти бсср ха + хе + 10х4+ 10хэ+ Зхэ + 2х+ 8 н Зхе+ 5х4 + Ох~ + 4х + 8, шоб 13, используя алгоритм Евклида для полиномов над полем целых чисел по ма пулю 13. Сначала запишем только коэффициенты для того, чтобы показать шаги алгоритма 11. 907 3050948 1060 310 7 080 7 О 128 80 9 01124 011 0 304 (5) Так что хэ + хе + 10х4 + 10хэ + Зхт + 2х + 8 равно (9хэ+ 7)(Зхе+ 5х4+ Охт+ 4х+ 8) + (11х4+ Зхт+ 4 Аналогично Зх~+ 5х +9хт+ 4х+8= (5хт+ 5)(11ха+Зхэ+ 4) + (4х+1); 11х4 + Зхэ + 4 = (бхэ + бхэ + 6х+ 5) (4х + 1) + 12; .
(6) 4х+1 = (9х+12) 12 + О. попс(йсо(н, п)) = а йсо(сопс(и), сопс(е)), рр(йсб(и(*),п(х))) = Ь 8сб(рр(и(х)),рр(е(х))), (7) где а и Ь вЂ” обратимые элементы. Здесь йод(и(х),и(х)) означает любой полинам от х, являющийся наибольшим общим делителем и(х) и п(х). Формулы (7) свсщят проблему поиска наибольшего общего делителя произвольных полиномов к поиску наибольшего общего делителя при.нншиенмх полиномов.
Алгоритм П деления полииомов над полем может быть обобщен для псеедаделенпл полиномов над любой алгебраической системой, представляющей собой коммутативное кольцо с единицей. Можно заметить, что алгоритм П требует явного деления только на 4(п), старший коэффициент — е(х) и шаг Р2 выполняется в точности гп — и+ 1 раз, Таким образом, если и(х) и п(х) начинаются с целых коэффициентов (Знак равенства здесь означает равенство по модулю 13, так как все арифметические действия над коэффициентами выполняются по модулю 13.) Проведенное вычисление показывает, что 12 является наибольшим общим делителем двух исходных полиномов. Так как любой ненулевой элемент поля представляет собой обратимый элемент области полиномов над полем, для полей принято делить результат выполнения алгоритма на его старший коэффициент, получая нормнроеаннма полипом, и именно его имеют в виду, говоря о наибольшем общем делителе (в орнгннале— ")э са!!ео гйе 8геатеэ! сопнпоп 6!ч!эог".— Лрим.
персе,) двух данных полиномов. бег(, вычисленный в (6), таким образом, оказывается равным 1, а не 12. Последний шаг в (6) может быть опущен, так как если с(ей(е) = О, то йсг((и(х),и(х)) = 1 безотносительно к выбору полинома п(х). В упр. 4 определяется среднее время работы алгоритма Евклида над случайными полииомами по модулю р. Вернемся к более общей ситуации, в которой полиномы даны над областью единственного разложения, не являющейся полем.
Из (4) можно вывести важные соотношения и если мы работаем над полем рациональных чисел, то едннствениыми делителями 1(н)"' "+г будут знаменатели фх) н г(х). Это наблюдение приводит к мысли, что всегда можно найти палиномы о(х) и г(х), такие, чта 1(и)'" "+ги(х) = й(х)и(х) + г(х), г(е8(г) < и, (8) где пг = г(е8(и) и и = г(еб(и), для любых полиномов и(х) и и(х) ф О при условии, чта иг > и. Алгоритм К (Псевдоде.авиве политиьков). Даиы полиномы и(х) =и х~+ '+игх+ив, о(х) =тьх +' '+игх+оо, гдеи„уь Оитп > и > О, Этоталгорнтм находитполнномы8(х) = д„, „х "+...+1о н г(х) = г„гх" ' + " + го, удовлетворяющие (8). К1. [Итерация по Ь.[ Выполнить шаг В2 для Ь = тл — и, т — и — 1,, 0; после этога алгоритм завершаетгзг, выдав ответ (г„г,..., го) = (и -ы ., ио) В2.
[Цикл умножения.) Установить сначала дь т- и„+ьоь, а затем — и; т- о„и— и +ьиу-ь для у =п+Й-1,п+Ь-2,...,О. (Приу < Ьэтоозначает чтои. +- о„и., поскольку мы рассматриваем и г, и з, ... как пули. Этих умножений можно избежать, если начать алгоритм с замены ит нас„'" " 'и, для О < г < тл-п.) $ Алгоритм Е (Обобщемимй влеориньи Евклида). Даны ненулевые полиномы и(х) и и(х) над областью единсгвеннога разложения Е, Алгоритм вычисляет наибольший общий делитель и(х) и о(х).
Предполагается существование вспомогательных алгоритмов для вычисления наибольшего общего делителя элементов 5, а также для деления а на Ь в Е при Ь ~ 0 и а, кратном Ь. Пример вычислений приведен ниже, в (10). Правильность алгоритма К легко доказать инлукцией по нг — и, поскольку при каждом выполнении шага К2, по сути, и(х) заменяется на с(и)и(х) — К(и)хье(х), где Ь = г(еб(и) — с(ей(о). Заметьте, что в алгоритме не использовано деление; коэффициенты й(х) и г(х) сами по себе представляют некоторые полиномиальные функции от коэффициентов и(х) и о(х). Если о„= 1, то алгоритм идентичен алгоритму Р, Если и(х) и и(х) — полиномы над областью единственного разложения, можно, как и ранее, доказать, что полиномы д(х) и г(х) — единственны, поэтому другой способ псевдоделения над областью единственного разложения состоит в умножении и(х) на о„"' "+' и применении алгоритма Р, если известно, что все частные на шаге Р2 будут существовать.
Алгоритм В может быть расширен до "обобщенного алгоритма Евклида" для примитнвяых полиномов вад областью единственного разложения следующим образом. Пусть и(х) н и(х) — примитивные полиномы с бей(и) > г(ей(и). Определим при помощи алгоритма В полинам г(х), удовлетворяющий (8). Теперь можно доказать, что 8сд(и(х), н(х)) = 8ст((о(х), т'(х)): любой общий делитель и(х) н и(х) делит и(х) и г(х); и обратно, любой общий делитель о(х) и г(х) делит Х(о) "+" и(х) и должен быть примитивным (поскольку примитивен о(х)), так чта ан делит и(х).
Если г(х) = О, имеем йсп(и(х),и(х)) = и(х); с другой стороны, если г(х) Ф О, из-за примитивности о(х) имеем 8сгг(и(х), г(х)) = йсг((и(х), рр(г(х)) ) „так что процесс может быть нтерирован. В качестве примера работы алгоритма Е вычислим бед полиномов и(х)ж ха + ха — Зх — Зхз + Яхт + 2х — 5, е(х) ж Зхв+ 5х4 — 4хз — 9х+21 (9) над целыми. Эти полиномы примитивны, так что на шаге Е1 устанавливается д +- 1. На шаге Е2 выполняем псевдоделение. 1 О -6 3050-4-921) 10 1 зо 3 3 0 5 О -2 О -6 ΠΠ— б -18 -18 0 -3 -3 8 2 -5 О -9 -9 24 б -15 О -4 — 9 21 О 3 6 -15 О 9 18 -45 О 0 О О 0 -5 О -15 0 О (10) О 9 18 -45 0 27 54 -135 0 24 54 -126 0 -15 0 -45 0 -ЗΠ— 15 О 3 О -9 Здесь частное 9(х) равно 1 Ззхт+ 0 31х+ -6.
Зе, Имеем 27и(х) = в(х) (9хз — 6) + (-15х4 + Зх» — 9), (11) Теперь шаг ЕЗ замещает и(х) на е(х) и е(х) на рр[г(х)) = 5х4 — хз + 3. Дальнейшие вычисления приведены в следующей таблице, в которой показаны только козффициенты. в(х) е( ') г(х) 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 Поучительно сравнить данные вычисления с вычислением того же наибольшего общего делителя над рациоиальиььии числами, а не над целыми, с использованием Е1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
