AOP_Tom2 (1021737), страница 212
Текст из файла (страница 212)
Разложение по модулю 2 представляет собой х(х+ 1) (х + х+ 1) и для нас бесполезно. Разложение па модулю 3 представляет собой (х + 2) (х + 2х + 2), а по модулю 5 — (х~+х+1)(х~+4х«2). Таким образом, искомый ответ — (х +х+1)(хз-х+2). 26. Начнем с Р «- (0...01), представляющего множество (О). Затем для 1 < / < г установим Р «- Р ~/ (Р «%- 4 ), где У означает побитовое «или"! а Р «и- 3( — побитовый сдвиг Р влево на 7! позиций. (В действительности достаточно работать только с битовым вектором размерности ((и+ 1)/2), поскольку и — гп содержится в множестве тогда и только тогда, когда в `ем содержита1 пь) 27.
В упр. 4 утверждается, что случайный полипом степени и неприводим по модулю р с весьма малой вероятностью, около 1/и. Но из китайской теоремы об остатках следует, что случайный нормированный полипом степени и над кольцом целых чисел будет приводим для каждого из Л различных простых чисел с вероятностью около (1 — 1/и), которая будет стремиться к нулю при )с -1 со. Следовательно, почти все полиномы иад кольцом целых чисел являются иеприводимыми для бесконечно большого количества простых чисел и почти все примитивные полиномы иад кольцом простых чисел являются неприводимыми полиномами (другое доказательство дано в работе %.
Б. Вго«рп, .4ММ 70 (19бЗ), 9б5-9б9). 28. См. упр. 4; вероятность составляет (3"](1+о«ря/ри1+озрх /р )(1+озря /р ) ., предельное значение при и -1 оо составляет д(3) = (1+ 3)(1+ -'3 И1+ 33 ) Для 1 < и < 10 искомые значения равны — -, —, — — — — — — (Пусть 1 3 7 37 73 173 !0) 127 1033 3 3 Ы ео ЫО 333 133 313 ЫЗО /(У) = Ла(1+ У) — У = 0(У ). Имеем д(3) = ехР(2 „>, 3"/и+ ~„„~, /(3"/и)) = Л(3)/(1 — «), и можно показать, что предельная вероятность равна Л(1) = ехр(х >1/(1/и)) е « .5б146. В действительности Н.
Г. де Брейн (Н. С. «!е Вгш!и) установил, что асимптотическая формула имеет следующий вид: !ппр о р — — е "+е «/и+0(п 3!обп). (См, Р. Н. ! еЛ«пег, Асга АпгЛ. 21 (1972), 379-388; Р. Н. Сгеепе ап«! Р. Е. Кап!5, МагЛ. !ог Зле Апа!уя!3 а/ А!Вогйлпш (Воз!оп: В1г!1ьапэег, 1981), 14.1.б.) с другой стороны, ответ для 1 < и < 10 при р ж 2 имеет меньшие значения: 1, «3 13 13 13~ 3«333: зы ф.
В работе А. Каор(шасйег апб Н, 15737!!шопе, Тгапэ. А«пег. Масй. Яос. 347 (1995), 2235 †22, показано, что для фиксированного р вероятность составляет ср + 0(1/и), где ср — — П >1 е Ы (1 + а р/р ) и с3 ж .397.) 29. Пусть 91(х) и 93(х) — любые неприводимые делители д(х). По китайской теореме об остатках (упр. 3) выбор случайного полинома !(х) степени < 27! эквивалентен выбору двух случайных полиномов !1(х) и !3(х) степени < 4 каждый, где 1,(х) = !(х) шос! 9,(х).
Наибольший общий делитель будет корректным множителем, если !1(х)!р -1У 3 шо«! 91(х) = 1 и !3(х)!р 1!73шо7!91(х) 73 1 или наоборот, и это условие выполняется в точности для 2((Р 1)/2)((Р + 1)/2) = (рж — 1)/2 выборов !1(х) и !3(х). Примечания. Здесь рассматривается только поведение с учетом двух неприводимых множителей, но истинное поведение, вероятно, гораздо лучше.
Предположим, что каждый иеприводимый множитель д,(х) имеет вероятность -' деления полинома !(х)13 — 1ыз — 1 для каждого !(х) независимо от поведения других д,(х) и !(х); предположим, что д(х) имеет всего г неприводимык множителей. Тогда, если закодировать каждый д,(х) последовательностью нулей и единиц в соответствии с тем, делит 91(х) или нет 3(х)73 1773 — 1 для последовательных проверяемых 1, можно получить случайный бинарный луч с г "листьями" (см. раздел б.З), Цена, связанная с внутренним узлом этого луча, который имеет гп листьев в качестве потомков, равиа 0(гпз(!обр)), а решением рекуррентного соотношения А„= (") + 2' " 2 ("„)Ар является А„= 2(") в соответствии с упр.
5.2.2 — Зб. Следовательно, сумма цеи данного случайного луча, представляющая ожидаемое время палкого разложения д(х), составляет 0(г1(!обр) ) при этих правдоподобных предположениях. Правдоподобность предположений становится абсолютно справедливой при выборе случайного г(х) степени < гй вместо того, чтобы ограничиться выбором палинома степени < 2й.
30. Пусть Т(х) = х+х" + +хв — след х и пусть о(х) = Т(!(х)) щойд(х). Поскольку г(х)г = г(х) в поле полиномиальных остатков по модулю д(х), имеем в этом поле о(х)г = а(х); другими словами, о(х) является одним из р корней уравнения дг — д = О. Значит, о(х) — целое числа Отсюда следует,. что П,":а бей(дэ(х),Т(г(х)) — е) = дэ(х). В частности, когда р = 2, можно, как в упр. 29, утверждать, что бей(дэ(х),Т(!(х))) будет собственным делителем дэ(х) с вероятностью > -', если де(х) имеет хотя бы два неприводимых множителя н !(х)— случайный бинарный полинам степени < 2й. [Заметьте, что Т(!(х)) шай д(х) может быть вычислено, начиная с и(х) +- !(х), и после установки й — 1 раз и(х) <- (г(х) + и(х)г) шой д(х).
Метод этого упражнения основан нв разложении палиномов хг — х = П," о (Т(х) — э), которое справедливо для любого р, в то время как формула (21) основана на разложении хг — х = х(х«к -«1!э + 1)(х!э -«1Ы вЂ” 1) для нечетных р.] "След" был введен Ричардом Дедекиндом (ВйсЬагй Пейей!пй), АЬЬапй!пщеп йег КЬ- и!3!. Севе!!эсйай йег г«!аэепэсйа!!еп ха Сойбпбеп 29 (1882), 1-56. Использование метода вычисления бей(/(х), Т(х) — в) для поиска множителей /(х) было прослежено до А, Эрвина (А. Агп!и), Агйг Гог Ма!., Аэгг. осЬ Еуэ. 14, 7 (1918), 1 — 46; однако его метод был не полон, потому что он не рассматривал Т(г(х)) для !(х) ,-~ х.
Алгоритм полного разложения с использованием следов был разработан позже Р. Д. Мак-Элисам (Н.. Л. МсЕ!«есе), Магб. Сошр. 23 (1969), 861 — 867; см, также «оп хпг Са1Ьеп апй БЬоир, Сошриэа!(апа! Сагир!ехйу 2 (1992), 187 — 224, алгоритм 3.6 (дающий асимптотически быстрые результаты). Генри Колен (Непп' СоЬеп) обнаружил, что при использовании этого метода для р = 2 достаточно проверить не более й специальных случаев !(х) = х, хэ, ..., хы '. Один из этих выборов г(х) гарантированно разбивает дэ(х) на множители, если дэ приводим, потому что можно получить результаты всех полинамов !(х) степени < 2й из этих частных случаев, если использовать тот факт, что Т(г(х)") ы Т(!(х)) и Т(и(х) + !(х)) гн Т(и(х)) + Т(!(х)) (по модулю де(х)), [А Соигэе !и Со«пригас!она! А!беЬгщс ХитЬег ТЬеогу (Ярг!пбег«1993), А!8опгЬш 3.4.8.] 31. Если и — элемент поля из р~ элементов, обозначим через й(о) с«пепень а, а именно— наименьший показатель степени е, такай, что пв = а.
Затем рассмотрим полинам Р„(х) = (х — а)(х — пг)... (х — аг «) = у (х)~Ы!'1, где д,„(х) — неприводимый полинам степени й(а). Прн а, пробегающем по всем элементам этого поля, соответствующий полинам д (х) пробегает по всем неприводимым полнномам степени е, делящим й, где каждая такая "неприводимость" встречается в точности е раэ.
Имеем (х+ !)О" — «!7« пюй д,„(х) = 1 тогда и только тогда, когда в пале (о+ !)!г В!э = 1. Если ! — целое числа, имеем й(а + !) = й(а); следовательно, и(р, й) в й ' раэ превышает 1 число элементов а степени й, таких, что аш -'Мэ = 1, Аналогично, если !«ЗЕ !ю нужна выяснить количества элементов степени й, таких, что (а+ !«)(г -«1/э = (а+ !з) (г~ — «)гэ или, что то же самое, Иа+ !«)/(а+ !з))!г В!э = 1, При а, пробегающем по всем элементам степени й, справедливо равенство (а+ !«)/(а+ !э) = 1+ (!« — гз)/(а + Гз). [Имеем п(р«й) = -'й ~„1 (3+ ( — 1)')р(с)(р ~' — 1), что составляет около половины общего числа "непрнводимостей' (в точности половину при нечетном й).
Это доказывает, чта бей(дэ(х), (х + !)Ы' — «Уэ — 1) дает хорошие шансы найти множители дэ(х) при фиксированном ! и случайным образом выбранном дэ(х); однако рандомизированный алгоритм предлагается для работы с гарантированной вероятностью для фиксироевинага дэ(х) и случайного 1, как в упр, 29.] 32. (а) Ясно, что х" — 1 = Пщ„Фэ(х), поскольку каждый комплексный и-й корень единицы является примитивным Ы-м корнем некоторого уникального о'1п. Второе тождество свелует из первого; Ф„(х) имеет целые коэффициенты, поскольку они выражшотся через члены произведений и частных нормированных полиномов с целыми коэффициентами.
(Ь) Условия, приведенного в указании, достаточно для доказательства того, что 1'(х) = Ф„(х). Когда р не делит и, имеем х" — 1 Г пх" ' по модулю р, гтедовательно, полипом х" — 1 свободен от квадратов по модулю р. При данных 7'(х) и (, таких, как описано в указания, обозначим через д(х) непрнводимый множитель Ф„(х), такой, что д(ье) = О. Если д(х) Эь ~(х), то ~(х) и д(х) — различные множители Ф (х). Значит, они являются различными множителями х" — 1 и, следовательно, не имеют неприводимык множителей по общему модулю р. Однако 6 является корнем д(х"), так что йсб(/(х),д(х~)) г- 1 над кольцом целых чисел, и поэтому 7(х) является делителем д(хе).
Согласно (5) 7(х)— делитель д(х) г по модулю р, а это противоречит предположению, что г" (х) и д(х) не имеют общих неприводимык множителей. Поэтому 7(х) = д(х). [Неприводимость Ф„(х) впервые была доказана для простых чисел и Гауссом в ОЫошэйюлеэ АПгйгпеИсю (Ье1рх(8, 1801), Ага 341, н Кронекером для произвольнык и в Х с1е Масй. Рогеэ ес Арр!10ндеэ 10 (1854), 177-192.] (с) Ф1(х) = х — 1, и при простом р Фр(х) = 1 + х + .
+ х" '. Если и ) 1 нечетно, нетрудно доказать, что Фэ (х) = Ф„(-х). Если р делит и, второе тождество в п. (а) показывает, что Фр„(х) = Ф„(хе). Если р не делит и, то имеем Фр„(х) = Ф„(хе)/Ф,(х). Для составного же и < 15 имеем Фа(х) = х~ + 1, Фе(х) = хг — х + 1, Фэ(х) = х + 1, Фэ(х) = е+ 3+1 Ф ( ) 4 3+ е +1 Ф ( ) 4, 2+1 1Р ( ) е э+ 4 3+хе +1 Фы(х) = т -х +х — х +х — х+1. [ФоРмУлУ Фгг(х) = (1+х" + +хне П")(х — 1)/(хе — 1) можно использовать для того, чтобы показать, что все коэффициенты Фж(х) равны ~1 или 0 при простых р и 9; однако коэффициенты Фгм(х) могут быть произвольно велики.] 33. Ложно; мы теРЯем все Р, с егч делимыми на Р. Истинно, если Р > бе8(и) [см. УпР.
36.] 34. [П. У. У. Уоп, Ргос. АСМ $углр. БутЬойс алд А!деЬгис Сотр. (1976), 26-35.] Установить (1(х),ет(х),ю1(х)) е- СОВ(и(х),и'(х)). Если 1(х) = 1, установить е <- 1; в противном случае устанавливать (и;(х), е,+1(х), ил+1(х)) +- ССВ(е,(х), ю,(х) — ь[(х)) для 1 = 1, 2,...,е — 1 до тек пор, пока не будет найдено ю,(х) — ь,'(х) = О. И наконец установить ие(х) + ев(х). Для доказательства корректности этого алгоритма заметим, что он вычисляет поли- номы 1(х) = иг(х)из(х) иэ(х) ..., е,(х) = и,(х)и,.~1(х)и;~г(х)...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
