Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 105
Текст из файла (страница 105)
Если и > 1 нечетко, нетрудно доказать, что Фт (х) = Ф„(-х). Если р делит и, второе тождество в п, (а) показывает, что Ф„„(х) = Ф„(хг), Если р не делит п, то имеем Фр„(х) = Ф (х")/Ф~(х) Для составного же и < 15 имеем Фт(х) = хт + 1, Фе(х) = хт — х+ 1, Фе(х) = х + 1, Фэ(х) = х +х +1 Ф!0(х) х х +х х+1 Ф$2(х) х х +1 Ф14(х) — х х +х х +х х+1 Фм(х) хе хт+хт х4+хз х+1. (шормулу Ф (х) = (14.хг+ .+хы пэ)(х — цу(хт — 1) можно использовать для того, чтобы показать, что все коэффициенты Фы(х) равны х1 или 0 при простых р и д, однако коэффициенты Фр „(х) могут быть произвольно велики.) ЗЗ. Ложно; мы теряем все р. с е;, делимыми на р.
Истинно, если р > беб(а) (см. упр. 36.) 34. [П. У. У. Уал, Ргос. АСМ зушр. зушЬо!!с влд А!Звбга!с Сошр. (1976)„26-35.) Установить (т(х),а1(х),ш1(х)) <- ССР(а(х),а'(х)). Если !(х) = 1., установить е +- 1; в противном случае устанавливать (а;(х), о,~~(х), шю+1 (х)) +- тдСП(о,(х), ш,(х) — и,'(х)) для 1 = 1, 2,..., е-1 до тек пор, пока не будет найдено ш„(х)-о,'(х) = О. И наконец установить а.(х) +- о,(х). Для доказателъства корректности этого алгоритма заметим, что он вычисляет поли- номы т(х) = а,(х)аз(х) ат(х)з..., е (х) = и (х)и, ~ (х)а+т(х)... и ач(х) =а';(х)аьы(х)а,.~т(х)...+2а;(х)аыы(х)штт(х)...+За,(х)апы(х)а~+э(х)...+ Имеем !(х) .!. ш1(х), поскольку неприводимый множитель а;(х) делит все, кроме а-го, члены ш1(х) и является взаимно простым по отношению к этому члену. Ясно и то, что а;(х) .!.
аоы(х). (Хотя в упр. 2, (Ь) доказывается, что большинство полиномов свободно от квадратов, на практике часто встречаются полиномы "с квадратами"; следовательно, этот метод становится весьма важным. Предложения по его усовершенствованию приводятся в Рап! 3. %елб апб Весту М. Ттайег, 3!СОМР 3 (1979), 300-305. Разложение по молулю р, свободное от квадратов, рассматривается также в ВасЬ алб ВЬа!!!т, А!ЗогЖишс г!пшбет ТЬеогу 1 (М1Т Ртезе, 1996), ответ к упр. 7.27.) 35. Имеем ш,(х) = Зсб(а,(х),ог(х)) Зоб(а!+,(х),а,(х)), где а'(х) = а,(х)а!~1(х)... и ат(х) = о!(х)е +1(х)... (Юнь отмечает, что время работы свободного от квадратов разложения по методу упр.
34 не более чем в два раза превышает время вычисления Зсо(а(х), а'(х)). Кроме тото, если дан произвольный метод свободного от квадратов разложения, метод из этого упражнения приводит к процедуре поиска наибольшего общего делитезш. (В случае, когда в(х) и о(х) свободны от квадратов, их наибольший общий делитель просто равен зоз(х), где ш(х) = и(х)е(х) = гез(х)юз(х); все полиномы из(х), о;(х), и;"(х) и о,'(х) свободны от квадратов.) Следовательно, задача преобразования примитивного полинома степени в в его свободное от ющлратов представление с точки зрения вычислений зкеиеаленглна задаче поиска наибольшего общего делителя двух полиномав степени н в смысле асимптотического времени работы для наихудшего случая,! 36.
Пусть Пз(х) — значение, вычисленное для "ку(х)" по процедуре иэ упр. 34. Если г)еб(сч)+ 2 бебе)+ = деб(и), то эз(х) = Пу(х) для всех у. Однако в общем случае у нас будет е < р и (/1(х) = П» „имзз(х) для 1 < у < р. Для дальнейшего разделения этик множителей можно вычислить 1(х)/(оз(х)Ггз(х) ... (/р-з(х)з ) = П >„и>(х)""' "" = х(х~). После рекурсивного поиска свободного от квадратов представления з(х) = (з1 (х), зз(х),...) получим зз(х) = )) < в +зь(х), так что можно вычислить отдельные и;(х) по формуле боб(П,(х),зз(х)) = из+за(х) для 1 < у < р. Полипом изь(х) останется, в то время как другие множители зз(х) будут удалены. Примечание. Эта процедура очень проста, но реализующая ее программа длинна. Если необходима короткая, а не предельно эффективная программа для полного разложения полиномов по модулю р, то, вероятно, проще будет модифицировать программу ь разложения с различными степенями так, чтобы она давала боб(хз — х, о(х)) несколько раз для одного и того же значения Н до тех пор, пока наибольший общий делитель не станет равным 1.
В этом случае нет необходимости начинать с вычисления боб(к(х),н'(х)) и удаления кратных множителей, как было предложено в тексте раздела, поскольку полипом хз — х свободен от квадратов. 37. точное значение вероятности составляет Цз>,(азз/рз)~з/йз!, где ьз — количество д„ равных /. Поскольку согласно упр. 4 азр/р" ж 1/», получим формулу из упр. 1.3.3-21. Примечания. Иэ этого упражнения следует, что если зафиксировать простое число р и случайным образом выбрать полипом к(х), то возникнет определенная вероятность его разложении указанным путем по модулю р. Более сложная задача состоит в определении вероятности при фиксированном полиноме и(х) и "случайном*' простом числе р, которое приводят к одному и тому же асимптотическому результату для почти всех и(х).
Г. Фробениус (О, ггоЬешпэ) доказал в 1680 году (хотя результат не был опубликован до 1896 года), что целый поливом и(х) разбивается по модулю р иа множители степени А,..., Ы„при случайным обрезом выбранном большом простом р с вероятностью, равной числу перестановок в группе Галуа С нз полиномов и(х), которые имеют длины циклов (А,...,4,), деленной на общее количество перестановок в гз. [Есзи и(х) имеет рациональные коэффициенты и различные корни бм..., 6„над полем комплексных чисел, его группа Галуа представляет собой единственную группу б~ перестановок, такую, что полипом Прп>...р< 1ес(з+ бз01Уз + + бе< 1У ) = С'(з,ум °,У ) имеет Рациональные коэффициенты и неприводим над полем рациональных чисел; см.
О. ггоЬешоз, ЯгзпвбэЬепсйге Кбл161 ргеиб. Айвз(. 1(г1ж (Вегйп, 1896), 689 — 703, Линейное отображение х ~-+ хз традиционно называется автоморфизмом Фробениуса, как в его знаменитой статье.) Кроме того, Б. Л. вандерВарден (В. 1., тапоегЖасчч(еп) доказал в 1934 году, что почти все полиномы степени и имеют множество всех и! перестановок в качестве ик группы Галуа (МагЛ. Алоэ(ев 109 (1934), 13-16). Поэтому почти все фиксированные неприводимые полиномы э(х) будут множителями, как можно ожидать, по отношению к случайному выбору большого простого числа р. (См.
также работу Х. СЬеЬогагет, Магй. Алла(ев 96 (1926), в которой представлено обобщение теоремы Фробениуса для сопряженнык классов групп Галуа,) 38. Из условий вытекает, что, когда ]х! = 1, мы имеем либо ]е -эх" э + - + оо! < ]ох-1]-1 < ]х" +к„1х" '], либо ]и зх" э+ .+эо! < и~-э — 1 < ]х" +и„хх" ~!. Поэтому согласно теореме Роше ]Х Есо!е Ро!усе«йене 21, 37 (1858), 1 — 34] и(х) имеет минкчум и - 1 или и — 2 корня внутри окружности ]х! = 1. Если и(х) приводим, он может бъпь записан как «(х) о»(х), где «и»« — нормированные целые полиномы. Произведения корней «и корней ш представляют собой ненулевые целые числа, так что каждый множитель имеет корень с абсолютной величиной > 1.
Следовательно, единственная возможность заключается в том, что «и ш оба имеют в точности по одному такому корню н что и„..1 — — О. Эти корни должны быть действительны, поскольку корнями являются комплексно-сопряженные числа. Значит, о(х) имеет действительный корень хо с ]хо! > 1. Но этого ие может быть, так как, если г = 1/хо, имеем 0 = ]1+ в„зге+ ° + и«г" ! > 1+ и„эгт — ]и„х ]г" — ° ° — ]но]гг > 1- [О.
Реггоп, Сге!!е 132 (1907), 288-307; обобщения даяы в А. Вгаоег, Ахаег. Х Ма!5. 70 (1948), 423-432, 73 (1951), 717-720.] 39. Сначала докажем утверждение из указания, Пусть полипом и(х) = а(х-а1)... (х-ои) имеет целые коэффициенты. Результант полинома и(х) с полиномом р — г(х) представляет собой детерминант, так что он является полиномом г»(р) = а»мэп!(у — Ф(сц))... (р — Ф(а )) с целымн коэффициентами (см. упр, 4.6.1-12). Если и(х) делит «(!(х)), то «(!(а1)) = О, Следовательно, г»(р) имеет общий множитель с «(р). Так что, если «неприводим, мм имеем йе6(и) = Йеб(г~) > Йеб(«).
Для данного неприводимого полинома и(х), для которого требуется короткое дош~- зателъство неприводимости, можно предположить его нормированность согласно упр. 18. а также считать, что 6«6(в) > 3. Идея заключается в том, чтобы показать существование полинома !(х), такого, что полипом «(р) ы г»(р) является неприводимым по критерию из упр. 38. Тогда все множители и(х) делят полином «(г(х)), и это доказывает, что о(х) неприводим. Доказательство будет "укорочено", если коэффициенты г(х) достаточно малы. Можно показать, что полипом «(р) = (р — 61)...
(р — !У ) удовлетворяет критерию упр 38, если и > 3 и !21 би ~ 0 и если выполняетск следующее "условие малости"; ]6!! < 1/(4п), за исключением случаев, когда ! = и или 6, = б„и ]И!У!! < 1/(4в). Вычисления производятся непосредственно, с учетом того факта, что ]ьъ! + + !«„! < (1+ ]А !) " (1 + Ф !). Пусть цм ..., и» вЂ” действителъные числа, а а»ем ..., о»+, — комплексные, где и = г + 2э и а»+»+! = о„~ь! для 1 < У < э. Рассмотрим линейные выражения 31(ао,... » аи-1)» определенные как 5!(2,", е' анз)) для 1 < / < г+ э и В(2 ",.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
