Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 17
Текст из файла (страница 17)
9. [Мйб] Пусть и — нечетное целое число н и > 3. Покажите, что если число 1(п) из теоремы 3.2,1.2В является делителем числа и — 1, но не равно и — 1, то и должно иметь вид р~рэ .рп где все р; — различные простые числа и $ > 3. ь 10. [Мйб) (Джон Селфридж (ЛоЬп Бе1(г166е).) Докажите, что если для любого простого делителя р числа и — 1 существует такое лю что х~" г шоб и 14 1, а к,", ' пэоб и = 1, то и — простое число.
11. [Мйй] Что выведет алгоритм Е, если Х = 197 209, й = $, т = 1? ~у . л нгш 991 пэя,'хж ип/] ь 12. [Мйй] Разработайте алгоритм, который, используя выходные данные алгоритма Е, на- ходит полходящнй простой множитель И, который обеспечивает возможность алгоритму Е формировать достаточно данных для вывода решения уравнения (16), 13 [дМ23] (Дж. Д. Диксон (3. 11. Ейхоп).) Докажите, что как только алгоритм из упр. 12 представляется решением (л, ее,..., е ), показатели степени в котором линейно зависят по молулю 2 от показателей степени в предыдущих решениях, когда число Х имеет различные простые множители, а величина х выбирается случайно, вероятность того, что разложение на простые множители не будет найдено, равна 2' ~. 14.
[М20] Докажите, что при выполнении шага ЕЗ алгоритма Е число Т никогда не кратно нечетному простому множителю р, для которого выполняется неравенство (йЛ)'г-'»' бр >1. ь 16. [М84] (Люка (Евсав) и Лемер (1,елпкт).) Положим, что Р и Я вЂ” взаимно простыецелыечисла нпустьУе ж 0: 11~ = 1, У„+~ = РП -ЦИ -~ прин > 1. Докажите чтоеслиХ— положительное целое число, взаимно простое с числом 2Р— 8Ц, и если Ц~~~ шоб Х = О, а (?~л ы»р пмк1 Х Р 0 для каждого простого числа р, делящего )т'+ 1, то )т' — простое число.
(В результате получаем метод проверки принадлежности чисел к простым числам в случае, когда известны делители числа йГ+ 1, а не делители числа Ю вЂ” 1. Значение 0 можно вычислить за О()об т) шагов, как в упр. 4.6,3-26.) [Указание, См. доказательство теоремы Ц 16. [Мбд] Бесконечно ли множество простых чисел Мерсенна? 17. [М25] (В. Р. Пратт (Ч. К. Ргаш).) Полное доказательство принацлежностн чисел к простым при поыощи обратной теоремы Ферма принимает вид дерева с узлами (4, я), где 4 и л — положительные целые чясла, удовлетворяющие следгющим условиям. (1) Если узлы (йпя~),, (йпя~) порождены узлом (4,х), то 4 = дм..ф + 1. [В частности, если (4,л) — младший потомок, то 4 = 2.] (й) Если уэлл (и 9) порожден узлом (4,л), то кш г»" шоб 4 Ф 1, (01) Для каждого узла (д, в) выполняется условие хт г шоб 4 = 1.
Из этих условий следует, что число д простое и х есть простой корень по модулю д лля всех узлов (д,*). [Например, дерево шоов, щ о,1$ с2,о (2,ь (2,1) г,э (З,э сЗ,ь ,Г (2,1) (3,2) (2,1) (2,1) ] (2, 1) показьшает, что 1(Ю9 — простое число.] Докажите, что подобное дерево с корнем (д,х) содержит не более у(д) узлов, где функция у довольно медленно возрастает. ь 18.
[ЯМ23] Приведите эвристическое доказательство соотношения (7) по аналогии с выводом соотношений (б), рассмотренных в этом разделе. Чему равна приближенная вероятность того, что р -~ < ~/р 7 ь 19. [Мйу] (Дж, М. Поллард (У. М. Ройэхб.) Покажите, как вычислить число М, которое делится на все нечетные простые множители р, такие, что р — 1 является делителем некоторого заданного числа )2. [Указание. Рассмотрите числа вида а" — 1.] Такое число М полезно при разложении чисел на простые множители, поскольку множитель числа Ф может быть получен в результате вычисления бес)(М,)д). Постарайтесь развить зту идею и сформулировать эффективный метод нахождения с высокой вероятностью простых множителей р данного числа У лля случая, когда все простые степенные множители для чисел р — 1 меньше 10, кроме, может быть, одного, меньшего 10 .
[Например, при помощи такого метода будет обнаружен второй по величине простой множитель, который делит (15), так как ои равен 1+ 2' ° бт б7 107 199 41231.] 20. [М40] Рассмотрите упр. 19, подставив в условие р+ 1 вместо р — 1. 21. ]М49] (Р. К. Ги (В. К. Сву).) Пусть ш(р) — число итераций, необходимых алгоритму В для выделения простого множителя р. Будет ли выполняться равенство яг(р) = 0(~р1оцр) при р -г сю7 ь 22. [МУО] (М. О. Рабин (М. О. ВаЬш).) Пусть для данного числа и р„— вероятность того, что алгоритм Р дает ошибочный результат.
Покажите, что р„< 1~ для всех и. 23. [Муу] . Символ Якоби (~~) по определению равен -1, 0 нли +1 для всех целых чисел р > О и всех нечетных целых чисел д > 1 в соответствии со следующим правилом: Я) и р~т Я (по модулю д), когда д — простое число, (я) = (д.)... (~.), когда чиню д равно произведению дп ..
д~ и 1 простых чисел (необязательно различных). Таким образом, символ Якоби является обобщением символа Лежандра (см. упр, 1.2.4-47). а) Докажите, что (") удовлетворяет следующим зависимостям, которые позволяют эфт е з "-г в фективно его вычислять: Я) = О; (~) = 1; (а) = (~ — „~-Я); („-) = (-1)~т Я (Эта-) = (") (е~-); (а) = (-1) ш мм пгь (я), если оба числа р и д нечетиы. [последняя закономерность, которая представляет собой обратную зависимость и сводит вычисление (Я) к вычислению (з), доказана в упр. 1.2.4 47(4) для р н д, являющихся простыми числами; поэтому в таком особом случае можно считать данную закономерность справедливой.] Ь) (Соловей (бо!отау) и Штрассен (бтгэээеп).) Докажите, что если и — нечетное число, но не простое, то количество целых чисел к, таких, что 1 < х < и и 0 ф (ф) ш х~" (по МоДУлю и), не пРевышает величины з 1г(п), (Значит, слеДУюшак пРоЦеДУРа с вероятностью, равной как минимум 1/2, для всех фиксированных чисел и корректно определяет, является ли данное число и простым.
"Сгенерировать случайное число к и интервале 1 < к < и. Если О Зз (я) ш х~'" Пгз (по модулю и), сказать, что и является, вероятно, простым; в противном случае сказать, что число и, определенно, не является простым.") с) (л. 1»1оньер (ь. м эшег).) Докажите, что если и и х — числа, для которых алгоритм Р делает вывод, что»п, вероятно, простое", то О ~ (-„") ш кы пуз (по модулю и). [Следовательио, алгоритм Р является основным при выполнении проверки в случае (Ь).] ь 24. [М00] (Л.
Здлемаи (1. Ай!ешап).) Если и > 1 и нечетно, а х > 1 — целое число, будем говорить, что чисао и "проходит проверку алгоритмом Р посредством к", если либо х шоб и м О, либо выполнение шагов Р2-Рб приводит к заключению, что число и, вероятно, простое.
Докажите, что для любого Н существуег множество положительных целых иечетных чисел хп, х < Н для щ < [)б Н], такое, что положителыюе нечетное целое число в интервале 1 < и < л! будет простым тогда и только тогда, когда оно проходит проверку елгоритмом Р посредством чисел х для х = к~ шоб и, ..., к = х, шоб и.
Таким образом, процесс вероятностной проверки "простоты", в принципе, может бъпь превращен в аффективный инструмент проверки, устраняющий всякие сомнения, (Сейчас ие требуется приводить зффективиый способ вычисления величин х~", нужно только доказать, что такие величины существуют.) 20. [НМ01) (Б. Рнман (В. Шещапп).) Докажите, что я(кпз) я(хыз) г* 01 Г» ~П+'»1Ы»г(! ;(к)+ — + — '+". =~ — 2~, ~ ' +О(1), 2 0 ' -/ !из .1 !+~ где суммирование выполняется по всем комплексным числам «+ !г, таким, что г > О и б(а + гг) = О, ь 26. [Мйб] (Г. К, Поклиигтон(Н. С. РосЫ!пбьоп), 1914.) Пустая = зг+1, где О < г < з+1.
Докажите, что число Ж будет простым тогда, когда для каждого простого делители р числа у существует такое целое число к, что к„[ шос! Н = бсс)(х»б " — 1, Ф) = 1. ь 27. [М80] Покажите, что существует способ проверки принадлежности к простым числам чисел вила !»' = б 2" + 1, использующий приблизительно столько же операций вычисления квадратов по мозблю Ф, сколько применялось в способе Люка-Лемера (1юсаз-ЬеЬшег) проверки чисел Мерсеина в теореме Е. [Указакие, См. предыдущее упражнение.] 20. [М07] .Для данных простого числа р и положительного целого числа И найдите значение фуикции 7'(р, И), среднее число случаев, когда число р делит Аз — 0В (учитывая кратность), если А и  — независимые случайные целые числа за исключением условия А (. В.
29. [Мйб] Докажите, что количество положительных целых чисел < и, простые множители которых принадлежат множеству простых чисел (ры..., р ), не меньше т"(г), если г м [!обл/!об р„] и р~ < . < р ЗО. [НМзз] (Дж. Д. Диксон (3. 1». П!хоп) и Клаус-Петер Шнорр (С)авз-Рееег ЯсЬиош).) Пусть р~ < < р,— простые числа, не делящие иечетиое число г1, и пусть г — четное целое число, не превышающее величины !обЮ/!«бр . Докажите, что количество целых чисел Х, принадлежащих интервалу О < Х < Ю и таких, что Х шос(д» = р",...р,'„, ие меньше пз"/г!.
Указание. Положите, что разложение числа Х на простые множители имеет вид 0~Д... Оз~». Покажите, что последовательность показателей (ем..., е, ) приводит к 2 решениям Х в случае выполнения неравенства е~ + . + е < г и что р ...р'„, есть квадратичный остаток по модулю о, при 1 < ! < 0. Такие погледовательности показателей могут быть вычислены как упорядочеиные пары (е'„..., е'; е",,, е'„',), где е[ + ° + ем < -,'т, е",+ "+е'„', < -,'г и (рг'...р»Г)йл 07 ш(р" ,...р' )йл пг (по подключу;) при 1 < ! < 3. 31. [М20] Испояьзуя результаты упр.
1.2.10-21, оцените вероятность того, что алгоритм разложения на простые множители Диксона (описанный перед изложением теоремы П) вычисляет менее чем 2т выходных значений. ь 32. [М21] Покажите, как улучшить ВБА-схему кодирования так, чтобы не было проблем с сообщениямн < ~/Л в том смысле, что длина сообщений не должна существенно увеличиться.
ЗЗ. [МЗО] Докажите или опровергните следующее утверждение; существует достаточно аффективный алгоритм, такой, что если для заданного числа Аг = ре, простые множители которого удовлетворяют условию р ш е гд 2 (по модулю 3), и заданного значения хз шоб А' он с вероятностью, не являющейся пренебрежимо малой, может найти значение х шоб И, то существует достаточно аффективный алгоритм, способный с подобной вероятностью найти множителя числа Х. [Если данное утверждение удастся доказать, зга будет означать не только то, что проблема кубического корня так же сложна, квк и проблема разложения на простые множители, но и то, что как ВЗА-схема, так и ЗС)ЗТ-схема обладают одним и тем же неустранимым недостатком.) 34. [Мур] (Петер Уайнбергер (Ретег %е!пбегйег).) Предпоеожим, что в ВВА-схеме И = рд н известно число гп, такое, что по меньшей мере для 10 'з всех положительных целых чисел я выполняется равенство хм шобИ = 1.
Поясните, как без больших трудностей решить задачу разложения на простые множители числа Аг, если число ш не слишком велико (схажем, ш < И ). ь Зб. [МЗЗ] (Х. К. Уильямс (Н, С. ЪЧ!!)!вгпв), 1979.) Пусть А' — произведение двух простых чисел р и д, где р шоб 8 = 3 и е шог! 8 = 7. Докалсите, что символ Якоби удовлетворяет равенству ( „*) = (уь) = -(ф), и используйте его для построения схемы кодирования и/иля декодирования, которая аналогична Б<2ЗТ-блоку Рабина, исключив при атом двусмысленность сообщений. 36.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
