AOP_Tom2 (1021737), страница 126
Текст из файла (страница 126)
Рабин (М. О. НаЬ!и).) Пусть для данного числа и р — вероятность того> что алгоритм Р дает ошибочный результат. Покажите, что р„< -' для всех и. 23. [М93[ „Символ Якоби (с) по определению равен — 1, 0 нли +1 лля всех целых чисел ч р > 0 и всех нечетных целых чисел (7 ) 1 в соответствии со следующим правилом: (е) гн р э 1 (по модулю (1), когда (7 — простое число, [Е) = (л-)... (д), когда число (7 равно произведению (7)... (7( и ! простых чисел (необязательно различных). Таким образом, символ Якоби является обобщением символа Лежандра (см.
упр. 1.2.4-47). а) Докажите, что (Г) удовлетворяет следующим зависимостям, которые позволяют эфч фективно его вычислять: (-) = 0; (1) = 1: [Е) = (~ — -'-Э); [-) = ( — 1)(а Огэ; (Га-) = (Е) ["-); (Г) = ( — 1)(е 0(а 01" (х), если оба числа р и (7 нечетны. [Последняя закономерность, которая представляет собой обратную зависимость и сводит вычисление (е) к э вычислению (Х), доказана в упр.
1.2.4-47((!) для р и (7) являющихся простыми числами, поэтому в таком особом случае можно считать данную закономерность справедливой.) Ь) (Соловей (Бо(оиау) и Штрассен (31гаээеи).) Докажите, что если и--нечетное число, но не простое, то количество целых чисел х, таких, что 1 < х < и и 0 ~ ( ~ ) сн х(" (по модулю и), не превышает величины 1ээ(и). (значит, следующая процедура с вероятностью, равной как минимум 1)(2, для всех фиксированных чисел и корректно определяет, является ли данное число и простым. "Сгенерировать случайное число х в интервале 1 < х < и.
Если О ~ (-*) еа х<" '>еэ (по модучю и), сказать, что и является, вероятно, простым; в противном случае сказать, что число и, определенно, не является простым.") с) (Л. Моньер (1. Моп(ег).) Докажите, что если и н х — числа, для которых алгоритм Р делает вывод, что "и, вероятно, простое", то О ~ ( — „*) = хш В1э (по модулю и). (Следовательно, алгоритм Р является основным при выполнении проверки в случае (Ь).[ ° 24.
[МЯб[ (Л. Эдлеман (Ь. АО1ешап).) Если и > 1 н нечетно, а х > 1 — целое число, будем говорить, что число и "проходит проверку алгоритмом Р посредством х", если либо х тес( и = О, либо выполнение шагов Р2-Рб приводит к заключению, что число и, вероятно, простое. Докажите, что для любого Х существует множество положительных целых нечетных чисел хм ..., х < Ж для т < [1й Х), такое, что положительное нечетное целое число в интервале 1 < и < 1У будет простым тогда и только тогда, когда оно проходит проверку алгоритмом Р посредством чисел х для х = х~ шоб и,, х = хм шод и.
Таким образом, процесс вероятностной проверки "простоты", в принципе, может быть превращен в эффективный инструмент проверки, устраняющий всякие сомнения. (Сейчас не требуется приводить эффективный способ вычисления величин х; нужно только доказать, что такие величины существуют.) 25. [ВМ41[ (Б. Риман (В К)ещапп).) Докажите, что я(хм~) я(х~~~) Г* Й Г ере' 1 "*с11 х(х)+ — + — *+ =// — — г~ '~ +О(1), 2 З ",/, (пе,/ „1+1г где суммирование выполяяется по всем комплексным числам а + 1г, таким, что т > О и ь(а+ 1г) = О. э 26. [Мйб] (Г. К. Поклингтон (Н.
С. РогМ1пйгои), 1914.) Пусть 1р' = /гч-1, где О < г < /+1. Докажите, что число 1У будет простым тогда, когда для каждого простого делителя р числа / существует такое целое число хр, что х~ ' щог( А' = йсд(х Р— 1, 1р') = 1. э 2Т. [МЯО[ Покажите, что существует способ проверки принадлежности к простым числам чисел вида 1е' = 5 2" + 1, игпользующий приблизительно столько же операций вычисления квадратов по модулю Ж, сколько применялось в способе Люка-Лемера (1 псаэ-ЬеЬшег) проверки чисел Мерсенна в теореме 1 . [Указание. См.
предыдущее упражнение.[ 29. [М27[ .Для данных простого числа р и положительного целого числа И найдите значение функции /(р,И), среднее число случаев, когда число р делит А — АВ (учитывая кратность), если А и  — независимые случайные целые числа за исключением условия А Ь В. 29. [Мйб[ Докажите, что количество патожительных целых чисел < и, простые множители которых принадлежат множеству простых чисел (рм..., р,), не меньше т"/гЬ если г = [1ояи/!ох рм) и р~ < < р,. ЗО.
[ВМЯЛА[ (Дж. Д. Диксон (3. Р. 111хоп) и Клаус-Петер Шнорр (С!апэ-Регег Бсйпогг).) Пусть р~ < < р — простые числа, не делящие нечетное число М, и пусть г — четное целое число, не превышающее величины (ой А/1ойр . Докажите, что количество целых чисел Х, пРинадлежащих интеРвалУ О < Х < Ю и таких, что Х гпоадг = Р['...Рм, не меньше т"/гЬ Указание. Положите, что разложение числа 1р' на простые множители имеет вид а, ...д„. Покажите, что последовательностыюкэзателей (ем ..,, е,) приводит А уэ к 2" решениям Х в случае выполнения неравенства е~ + + е < г и что р",... р' есть квадратичный остаток по модулю а, при 1 < и < аЬ Такие последовательности показателей могут быть вычислены как упорядоченные нары (еь..., е'; е",,..., е" ), где е', +.
+е',„< зг,е,+ . +е',„<-'ги (р~'...р )йп П~ = (р,' ...р )бь П (по модулю о) при 1 < г < 8. 31. [М80[ Используя результаты упр. 1.2.10-21, оцените вероятность того,что алгоризм разложения на простые множители Диксона (описанный перед изложением теоремы П) вычисляет менее чем 2пз выходных значений.
ь 32. [ЛЩ Покажите, как улучшить 118А-схему кодирования так, чтобы не было проблем с сообщениями < ~/Х в том смысле, что длина сообщений ие должна существенно увеличиться, 33. [М50[ Докажите или опровергните следующее утверждение: существует достаточно эффективный алгоритм, такой, что если для заданного числа Ж = рд, простые множители которого удовлетворяют условию р щ 9 ш 2 (по модулю 3), и заданного значения х ьзоб Ю он с вероятностью, не являющейся пренебрежимо малой, может найти значение з шоб Ю, то существует достаточно эффективный алгоритм, способный с подобной вероятностью найти множители числа !У.
[Если данное утверждение удастся доказать, это будет означать не только то, что проблема кубического корня так же сложна, как и проблема разложения на простые множители, но и то, что как ВЯЛ-схема, так и 51)йТ-схема обладают одним н тем же неустранимым недостатком.] 34.
[М80[ (Петер Уайнбергер (Регег Ъе!пЬегйег).) Предположим, что в ВВА-гхеме )у = рд н известно число т, такое, что по меньшей мере для 10 '~ всех положительных целых чисел х выполняется равенство к"' шод Х = 1. Поясните, как без больших трудностей решить задачу разложения иа простые множители числа Н, если число гл не слишком велико (скажем, т < !у ~ ). ° 35. [М85) (Х. К. Уильямс (Н.
С. ЪЧ!!!!ашв), 1979.) Пусть й'- — произведение двух простых чисел р и д, где р шос(8 = 3 и д шоб 8 = 7. Докажите, что символ Якоби удовлетворяет равенству ( ~,,*) = (я) = — ( я ), и используйте его для построения схемы кодирования и/или декодирования, которая аналогична бг)11Т-блоку Рабина, исключив при этом двусмысленность сообщений. 36. [НЛЩ[ Асимптотическая оценка времени выполнении алгоритма Е в виде уравнения (22) является слишком грубой для того, чтобы использовать ее ддя получения осмысленных значений числа й, если только оно не является очень большим, поскольку при значениях числа !У, с которыми обычно приходится иметь дело, величина !и!вН всегда сравнительно мала.
Выполните более тонкий анализ, позволяющий уточнить поведение уравнения (22) для приемлемых значений числа )у. Поясните также, как выбирать значение 1п т, минимизирующее (22), за исключением случаев, когда множитель достигает величины ехр(0(!об 1о8 !т')). 37.
[М87) Докажите, что квадратный корень из любого положительного целого числа 77, если только оно не является точным квадратом, имеет периодическую цепную дробь вида чЪ ж Н+ //а,,..., а„,2Н,ап,.,, о„,2Н,а,,... а„,2Н,... //, где Н = [4Р) н (ап...,а„) — палиндром (т. е, симметричная последовательность а, = а„~ь~, при 1 < 1 < и) 38.
[85) (Ньшересиме простые числа.) Для 0 < 8 < 9 найдите наиболыпее 50-разрядное простое число Ра, которое содержит максимально возможное количество десятичных раз- рядов, равных 4. (Сначала найдите максимум по 4, а затем — наибольшее такое число ) 39. [40[ Для многих простых чисел р характерно свойство, состоящее в том, что числа 2р+ 1 также являются простыми, например 5 -э 11 э 23 -э 47. Обобщая, можно сказать, что число 9 — преемник числа р, если ри 9 — оба простые числа ну = 2 р+1 для некоторого ь )г > О.
Например, 2 -+ 3 — г 7 -+ 29 — г 59 -г 1889 -г 3779 — г 7559 -г 4058207223809 -+ 32465657790 473 -+ 4462046030502692971872257 -г 95(30 разрядов пропущено)37-+ наименьший преемник для числа 95... 37 содержит 103 цифры. Найдите максимально длинную цепочку преемников простых чисел. э 40.
[Муб[ (Л. Шамир (А. БЬагп!г).) Рассмотрим абстрактный автомат, который может в течение одного цикла выполнять операции х+ у, х — у, х у и [х1'у) над целыми числами х и у произвольной длины; длина таких чисел не имеет значения. Автомат хранит их в памяти с произвольным доступом н может выбирать для выполнения операций различные шаги программы в зависимости от того, будет ли для заданных чисел х и у выполняться равенство х = у.
Назначение данного упражнения — показать, что в таком автомате можно применить изумительно быстрый способ разложения чисел на простые множители. (Поэтому, вероятно, будет достаточно трудно показать, что на реальных компьютерах разложение на простые множители выполнить исключительно сложно, хотя мы и подозреваем, что это так.) а) Для заданного целого числа и > 2 найдите способ вычисления на таком гипотетическом автомате величины и! за 0(!ойп) циклов.
[Указание, Если А — достаточно большое целое число, то биномиальные коэффициенты („) = т!/(т — й)! Ы можно легко вычислить по значению числа (А + 1) Ь) Покажите, как на таком автомате вычислить число 7(п) за 0(!ой и) циклов для заданного целого значения и > 2 со следующими свойствами: 7(п) = и, если и — простое число, в противном случае /(и) — собственный делитель (необязательно простой) числа и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
