Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 104
Текст из файла (страница 104)
упр, 4.6.1-12), и кратные множители по модулю р существуют тогда н только тогда, когда р делят этот днскриминант. (Разложенне (22) по модулю 3 равно (х + 1)(х — х - 1) (х + хэ - х + 1); квкзратные множители для этого полннома имеются только д,пг р 3, 23, 233 и 121702457. Натрут доказать, что нанменыпее простое число, не являющееся "неудачным", не превышает 0(п 1об)т'и), если п = бей(и), а Х является гранью по абсолютной величине коэффнцнентов э(х ).] 24. Умножьте нормированный полнном с рапнональнымн коэффициентами на подходящее ненулевое целое число для получения примитивного полннома над кольцом целых чисел.
Разложите полипом над кольцом целых чисел, а затем конвертнруйте множители в нормированные полнномы (таким образом, не будет потеряно ни одно разложение; см. упр. 4.6.1-8). 2$. Рассмотрение постоянного члена показывает, что у полинома нет множителей степени 1, так что если полипом приводим, то он должен иметь адин множитель степени 2 и один — степени 3. Разложение по модулю 2 предстаэляет собой х(х+ 1)э(х~ + х+ 1) н для нвс бесполезно. Разложение по модулю 3 представляет собой (х+ 2) (х + 2х+ 2), а по модулю Ь вЂ” (х +я+1)(х +4х+2). Таким образом, искомый ответ — (хз+х+1)(хэ-х+2).
26. Начнем с Р» — (0...01), представляюшего множество (О). Затем для 1 <,у < г установим Р»- Р Ч (Р Ф- г(1), где Ч означает побитовое "или", а Р Ш- »! — побитовый сдвиг Р влево на б позиций. (В действительности достаточно работать только с битовым вектором размерности ((и+ 1)/2), поскольку и — гп содержится в множестве тогда и только тогда, когда в нем содержится т.) 27. В упр. 4 утверждается, что случайный полипом степени и неприводим по модулю р с весьма малой вероятностью, около 1/и. Но из китайской теоремы об остатках следует, что случайный нормированный поливом степени и над коль»»ом целых чисел будет приводим для каждого из Л различных простых чисел с вероятностью около (1-1/п) ", которая будет стремнтьгл к нулю при й -» оо.
Следовательно, почти все полиномы над кольцом пелых чисел япляются непривадимыми для бесконечно большого количества простых чисел и почти все примитивные полиномы нед колы»ом простых чисел являютсн непрнводнмыми полиномами (другое доказательство дано в работе %. Я. Вготи, АММ 70 (1963), 965-969).
26. См. упр, 4; вероатность составляет [х") (1+а»гх/р)(1+о»эх'/р~)(1+а»эх~/р')..., пре- дельное значение при и -» оо составляет д(х) = (1+я)(1+ -х )(1+ эх ).... Для э г 3г1»э пэ»о»»эг»шз 1 < и < 10 яскомые значения равны 1, е, рэй~ ео Пб Йб»ы пе ы»е' [Пусть /(д) = 1п(1+ 9) — д = 0(дэ). Имеем д(х) = ехрД „> х"/и+ ~ >, У(х"/и)) = Л(х)/(1 — х), и можно показать, что предельная вероятность равна Л(1) = екр(х „>»У(1/и)) е т ж .$6146. В действительности Н. Г. де Брейн (Н.
С. бе Впщп) усп»повил, что асимптотнческав фоРмУла имеет следУющий вид; !ппр-,;»» а г = е т+е '/и+0(п 1ой и). [См. Р. Н. 1.ейшег, Асса Аг!1Ь. 21 (1972), 379-366! Р. Н. Сгеепе апб Р. Е. Кпшй, Маей. гог гЬе Апа)уэ!э ог" А!дштйЬшэ (Вштоп: В!г!»)»анвера, 1981), 14.1.6.) С другой стороны, ответ ,Вла 1 < и < 10 ПРИ Р 2 имеет меньшие Значении: 1»~ э. 74»е»е, 3» 1»эе, эьэз ф. В работе А. Кнор(шасЬш апд В, ЪЧш!!шопз, Тгалэ. Ашаг. Маей. оыос. 347 (1995), 2236-2243, показано, что для фиксированного р вероятность составляет с> + 0(1/п), где ср —- 1'[ >, е" Ы (1+а г/р ) и сэ ж.397.) 29.
Пусть д»(х) и дэ(х) — любые неприводимые делители д(х). По китайской теореме об остатках (упр. 3) выбор случайного полинома 1(х) степени < 2о' эквивалентен выбору двух случайных поляномов 1»(х) и 1э(х) степени < г! каждый, где й(х) = 1(х) шоб 1,(х). Наи- больший обшнй делитель будет корректным множителем, если 1»(х)Ы -МГ» шог! 9»(х) .
1 и Гэ(х)Ш мышобд»(х) ф 1 или наоборот, и зто условие выполняется в точности для 2((р~ — 1)/2)((р + 1)/2) = (рз" — 1)/2 выборов 1»(х) и гэ(х). Прпыечанвл. Здесь рассматривается только поведение с учетом двух неприводимых множителей, но истинное поведение, вероятно, гораздо лучше, Предположим, что каждый » неприводимый множитель д,(х) имеет вероятность 1 деления полннома 1(х)Ы -ц/э — 1 для каждого 1(х) независимо от поведения других д (х) н 1(х); предположим, что д(х) имеет всего г неприводимых множителей. Тогда, если закодировать каждый д»(х) последо- вательностью нулей и единиц в соответствии с тем, делит д;(х) или нет 1(х)!г -цгз — 1 для последовательных проверяемых 1, можно получить случайный бинарный луч с г "листьями" (см, раздел 6.3). Цена, связанная с внутренним узлом этого луча, который имеет т листьев в качестве потомков, равна 0(ш'(!обр)), а решением рекуррентного соотношения А„= (") + 2' " 2 (") А» является А„= 2(") в соответствии с упр.
5.2.2-36. Следовательно, сумма цен данного случайного луча, представляющая ожцдаемое время па»ного разложения д(х), составляет О(г~(!ойр)э) при этих правдоподобных предположе- ниях. Правдоподобность предположений становится абсолютно справедливой при выборе случайного й(х) степени < ггй вместо того, чтобы ограничиться выбором полинома степени < 24.
30. Пусть Т(х) = я+хе+ +хе — след х и пусть ч(х) = Т(й(х)) шобу(х). Поскольку й(х)г = й(х) в поле полииомиальных остатков по модулю у(х), имеем в этом поле е(х)г = е(х); другими словами, г(х) является одним из р корней уравнения уг — у ж О. Значит, ч(х) — целое число. О~сюда следует, что Д," е бег>(уг(х), Т(й(х)) — г) = уг(х). В частяости, когда р = 2, можно, как в упр.
29, утверждать, что бес>(дг(х), Т(й(х))) будет собственным делителем дг(х) с вероятностью Е 1, если уг(х) имеет хотя бы два иеприводимых множителю и й(х)— случайиый бинарный поливом степени < 24. (Заметьте, что Т(й(х)) шо>>у(х) может быть вычислено, иачиная с и(х) +- й(х), и после установки д — 1 раз и(х) +- (й(х) + и(х) г) шоб у(х). Метод этого упражнения основан на разложении полииомов хг — х = Пг '(Т(х) — г), которое справедливо для любого р, в то г ч ч время как формула (21) основана на разложеиии х> — х ж х(х>г ->уэ + 1)(х>г -г>/э — 1) для нечетнмх р,) "След" был введен Ричардом Дедекиидом (В>сЬэгб Пебейпб), АЬЬащИипдеп бег Кблйд!. СеэеНгсЬай бег 1ризе~жйайеп хп Сбйййпуел 29 (1882), 1-56. Использование метода вычисления бей>(у(х), Т(х) — г) для поиска множителей й'(х) было прослежено до А.
Эрвина (А. Агм>п), АгМч Гог Май., Агбк осЬ Руз. 14, 7 (1918), 1-46; однако его метод был не полон, потому что ои ие рассматривал Т(й(х)) для й(х);4 х. Алгоритм полиого разложения с использованием следов был разработан позже Р. Д, Мак-Элисом (Е. Л. МсЕ1>есе), МайЛ. Сотр. 23 (1969), 861-867; см. также топ гш СайЬеп апг> ЗЬопр, Соп>ршаИола> Сошрйехййу 2 (1992), 187-224, алгоритм 3,6 (дающий асимптотически быстрые результаты). Генри Колен (Непп' СоЬеп) обнаружил, что при использовании этого метода для р ж 2 достаточно проверить ие более д специэльиых случаев й(х) = х, хг,..., хг~ '.
Один из этих выборов й(х) гарантироваиио разбивает уг(х) иа миозсители, если дг приэапгм, потому что можно получить результаты всех полиномов й(х) степеии < 24 из этих частных случаев, если использовать тот факт, что Т(й(х)г) щ Т(й(х)) и Т(и(х) + й(х)) щ Т(и(х)) + Т(й(х)) (по модулю дг(х)). (А Союзе щ Сошрийаййопвй Айуебга>с >чпщбег ТЬеогу (Яргшйег, 1993), А!бог>ййш 3.4,8.) 31, Если а — элемепт поля из р~ элементов, обозначим через д(а) сща>гиь а, а именно— наимеиьший показатель степени е, такой, что аг = а. Затем рассмотрим полипом Р (х) — (х — а)(х — аг) (х — аг ) — д (х) > > > где д (х) — иеприводимый полипом степени д(а). При а, пробегающем по всем злемеятам этого поля, соответствующий полинам д (х) пробепыт по всем неприводимым полииомам степени е, делящим д, где каждая такая "иеприводимость" встречается в точности е раз.
Имеем (х+ й)йг -'>>г шой> у (х) = 1 тогда и только тогда, когда в поле (а+ й)йг '>>~ = 1. Если й — целое число, имеем д(а+ 1) = Ы(а)> следовательно, п(р,д) в д ' рзз превышает число элементов а степени д, таких, что айг -'>>э = 1. Аиэлогично, если й, йй йэ, иужио выяснить количество элементов степени д, таких, что (а+ й> ) Ы - >»э = (а+ йг) йг -'>>г или, что то же самое, ((а+ й~)/(а+ йг))йг -»lг = 1.
При а, пробегающем по всем элемеитам степени д, справедливо равенство (а + 1г)/(а + йг) = 1 + (й> — йг)/(а + йг). (Имеем ц(Р, д) = ~~д ' 4„,>г(3+ ( — 1)")Д(с)(Р ~' — 1), что составлает около половины общего числа "неприводимостей" (в точности половицу при нечетном д).
Это доказывает, что бсб(дг(х), (х + й)ы -ш' — 1) дает хорошие шансы найти множители д>(х) при фиксированном й и случайным образом выбранном уг(х)> однако раядомизированиый алгоритм предлагается для работы с гарантированной вероятностью для фиксцрованиеге дг(х) и случайиеге й, как в упр. 29.) 33. (а) Ясно, что х" -1 ы П„„Фе(х), поскольку каждый комплексный и-й корень единицы является примитивяъ~м 6-и корнем некоторою уникального г(!п.
Второе тождество следует из первого; Ф„(х) имеет целые коэффициенты, поскольку они выражаются через члены произведений и частных нормированных полиномов с целъпеи коэффициентами. (Ь) Условия, приведенного в указании, достаточно для доказательства того, что !(х) = Ф„(х). Когда р не делит и, имеем х" — 1 .!. пх" ' по модулю р, следователъно, полипом х" — 1 свободен от квадратов по модулю р. При данных 1(х) и 4, тякик, как описано в указании, обозначим через д(х) неприводимый множитель Ф„(х), такой, что д(~") = О. Если д(х) ~ Дх), то У(х) и д(х) — различные множители Ф„(х). Значит, они являются различными множнтелями х" — 1 и, следовательно, не имеют неприводимык множителей по общему модулю р. Однако ~ является корнем д(хг), так что Зоб(у(х), д(х")) 14 ! нед колыши целых чисел, и поэтому 7(х) является делителем д(хг).
Согласно (5) !(х)— делитель д(х)" по модулю р, а это противоречит предположению, что у(х) и д(х) не имеют общих неприводимых множителей. Поэтому у(х) = д(х). (Непрнводимость Ф„(х) впервые была доказана для простых чисел и Гауссом в Вбздшит!олез АптИшебсш (Ье(рэ!3, 1801), Ага 341, и Кронекером лля произвольных и в Х г(е Маей, Рагез ет Арр!79идее 19 (1854), 177-192.) (с) Ф1(х) = х — 1, и при простом р Ф„(х) = 1+ х+ . + х' '.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
