Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 94
Текст из файла (страница 94)
Поэтому ег =1 не~ =1. Замечание. Для того чтобы выполняемая проверка оказалась зФфектияной, следует подбирать Р и Я таким образом, чтобы проверка выполнялась с некоторой оероятностью. Лемер (ЬеЬшег) предложил выбрать Р = 1, чтобы Р 1-4ф а Я выбрать таким образом, чтобы Л'.Ь ЯР.
(Если последнее условие не соблюдается, значит, число Х не простое, если только выполняется условие ~ЦР~ < К) Далее, из приведенного выше рассуждения видно, чта желательно иметь е1 = 1, т. е. Р~~ пгэ ш — 1 (по модулю л'), это еще одно условие, налагаемое на выбор 1О. Если Р удовлетворяет этому условию н если Кч+г шаб Л' ,"Е О, то известно, что Х вЂ” не простое. Пример. Если Р = 1 и О = -1, та получаем последовательность Фибоначчи и Р = Ь.
Поскольку 5'~ ьз -1 (по модулю 23), молгно было бы попытаться доказать, что 23— простое число, используя последовательность Фибоначчи: (Р„шоб23) = 0,1,1,2,3,3,8,13,21,11,9,20,6,3,9,12,21,10,3,18,3,21,1,22,0,... Поэтому 24 есть рант появления 23, и проверка сработала. Однако при помощи последовательности Фибоначчи не удается установить подобным образом тот Факт, что числа 13 и 17 — простые, так как гг шоб 13 = 0 и Ре шо«! 17 = О. Если р и х1 (по модулю 10), то 5Щ П««шос(р = 1 и, следовательно, Р «(но не Ра ы) делится на р.
17. Пусть /(д) = 2 !8 д — 1. Если д = 2 нлн 3, то дерево содержит не более /( !) узлов. Для простого числ» 9 > 3 положим 9 = 1 + ®... Фь где «> 2, а Ф, ..., Ф вЂ” простые числа. Размер дерева < 1 + 2 /(94) = 2+ /(9 — 1) — «< /(9). (о(СОМР 7 (1975), 214-220.] 18. Величина х(С(а) — Г(о)) равна количеству таких и < х, для которых второй по величине простой множитель не превышает к", а наибольший по величине простой множитель > х . Следовательно, С'(«)8 = (.( "")-я(х')) х'-'(С(«Д1 - «)) - Р(«/(1 - ))). Вероятность того, что рг-«< ьфс, равна /е г'(«/2(1 — «))« ' «««. (Кстати, можно показать, что она равна / г («/(! — «)) 8«, т, е, среднему значению величины !обр«/!о8 х; она равна и ! константе Дикмаиа Голомба (В!с!«шап-Со!ошЬ) .62433, приведенной в упр.
1 3 3-23 и 3 1-13. Можно показать также, что производная Са(0) равна / г («/(1 — «))«г ««« = г (1) + 2г (2«) + зу(31) + ° = е . Для третьего по величине простого множителя Н(а) = уе (Н(«/(1-«))-С(«/(1-«)))« '«««, а Н" (О) = оо. См. Р. В!!!!пбе!еу, Репо««. Ма«Л, Нппбаг. 2 (1972), 283-289; Л. Са(ашЬое, Асса АгйЛ. 31 (1976), 213 — 218; (у. Е. Кпи«!«, Ь. ТгаЬЬ Раббе, ТЛеоге«!са! Сошр, Яс!. 3 (1976), 321-348; Я. Е.
На(пег, К. Я. МсСпг!еу, Х А!8пп«Лпм 10 (1989), 531-556.) 19. Число М = 2п — 1 кратно всем числам р, ддя которых порядок 2 по модулю р делит число 27. Разовьем зту клею, положив а« = 2 и о«ь« = а ' шобХ, где 42 = р/, и е р«есть 2-е простое число н е« = (!об!000/!обр«). Пусть А = а«ее. Вычислим теперь Ьр — — боб(А" — 1, Х) для всех простых чисел 9, расположенных между 10з и 1Оз. Зто можно сделать, если начать вычисления с числа А'ом шо«! М, а затем умножить его на А~ шо«! Х или А~ шо«! Х (Похожий метод в 1920 году применил Д.
Н. Лемер (!Э. Х, [.ейшег), но он ие опубликовал результатов.) Так же, как и в алгоритме В, можно путем группирования исключить из рассмотрения почти все наибольшие общие делители; например, поскольку Ьзе, ь бес((Аю" — А", Х), можно использовать группы нз 8, вычисляя сначала с„= (Азе' — Аы)(А«е' — Ащ)... (Аю' — А) шо«! Л«, а затем — 8сс!(с„, Ю) для 33 < г < 3334. 20. См. Н, С. %!!!!аше, Ма«Л. Сошр. 39 (1982), 225-234. 21.
Интересная теория, имеющая отноп«ение к условиям втой задачи, была предложена Зриком Бахом (Епс Вас!«), (пГогша«!оп ап««Сошрв«а«!оп 90 (1991), 139-155. 22, Алгоритм Р не достигает цели только тогда, когда для случайного числа в не подтверждается тот Факт, что число и не простое. Будем называть число х плохим, если хг шо««п = 1 илн одно из чисел хм« удовлетворяет условию ьз -1 (по модулю и) для 0 < у < Л. Поскольку число 1 плохое, получаем р = (܄— 1)/(и — 2) < Ь„/(и — 1), где ܄— количество плохих чисел х; „таких„что 1 < х; < и, если число и ие является простым. Каждое плохое число х удовлетворяет условию*" ' ш 1 (по модулю и).
Если число р простое, число решений уравнения вг щ 1 (по модулю р') для 1 < х < р' равно числу решений уравнения 99 ш 0 (по модулю р' '(р — 1)) для 0 < у < р' '(р — 1), т. е. 8сб(9, р' '(р — 1)), поскольку можно заменить чвсло я числом а", где а — простой корень. Пусть и = и",... и,'., где все и; — различные простые числа. Согласно китайской теореме об остатках число решений уравнения а" ' щ 1 (по модулю и) раню П;„«8сб( -1,," '(и« -1Н, н таких решений не более чем 11ы,(п< — ц, поскольку число и; взаимно просто с и — !.
Если некоторое е, > 1, то и, — 1 < 3 и',.' и, следовательно, число решений не превышает хи; в этом случае Ь„< ~3п < 1(п — Ц, ибо и > 9. В связи с этим можно положить, что число и равно произведению пы .. п„различных простыхчисел. Пустьп, =1+2ЫОпгдей~ < . <й,. Отсюдаполучаембсб(п — 1,п,— ц = 2~'д,', где й,' = ппп(й, й;) и 4,' = бсб(9,9;), При модуле н, количество таких х, для которых выполняется условие хе ш 1, равно 4о а количество чисел я, для которых х э ш -1, фэ равно 2'д, 'при О < 2 < й, 'и О в противном случае. Поскольку й > йм то Ь„= В' " 9', (1+ Ееб! <„, 2').
Для завершения доказательства достаточно показать, что Ь„< 19ы .. 4,2"'+"'+"' = тг(п), так как р(п) < и — 1. Отсюда получаем (1 + Ееб!сь, 2")/2 '+"'+ь" < (! + Е , 2")/2 " = 1Дг" — Ц + (2 — 2)/(2' (2" — Ц) < 1/2 -', Следовательно, если не выполняются равенства г = 2 и й~ = йз, получаем результат. Для г = 2 в упр.
9 показано, что число и — 1 не кратно как числу п~ — 1, так и числу пз — 1. Значит, если й~ = йз, то нельзя получить равенства 9( — — у н 9э = Оз; отсюда следует, что в этом случае 4(вз < -'айвз и Ь„< 1ер(п). [Сы. Х !ЧвшЬег Хйеогу 12 (1980), 128-138.) Из этого доказательства сле!Очт, что число р близко к -,' только в двух случаях: когда число и равно (1+ 2В)(1+ 44~) н когда оно является числом Кармайкла специального вида (1+ 29~)(1+ 2дз)(1+ 24з). Например, для и = 49939 99877 получаем Ь„= -(49938 99876) и р„ш .24999; если н = 1667.
2143. 4523, той„= 1(1666 2142.4522), р„ш.24968. Допатнительные примечании приведены в ответе к следующему упражнению. 23. (а) Доказательства для всех случаев, кроме, может быть, случая закона обратимости, выполняются просто, Пусть р = ры ..р, и 9 = ш... д„где все р; и 4! — простые числа. Тогда (Р) Д(Й) Д» ц!ш-ндш-!У4 (44) ( цХ.с ш'-Он'-1)/~ (Я) Я,, 41,, р' р так что остается. только убедиться в том, что ~,4 (р, — Ц(чу — Ц/4 ш (р — Ц(ч Ц/4 (по модулю 2).
Но ~",, (р, — ц(4 — ц/4 = (2„,(р; — ц/2)(2, (Ор — ц/2) будет нечетной тогда и только тогда, когда для нечетного количества чисел р; и 9! выполняется ш 3 (по модулю 4), а это происходит тогда н только тогда, когда число (р — 1)(д — Ц/4 нечетно. (С. С. Л. ЛасоЬ1, Вег!сйг Кбшб!. Ргеи8. Айад. Ьгйшш Вег!т 2 (1837), 127-136; В. А.
Лебег (У. А. 1 еЬез8ве) в !. Ма1Л. Ригее Арр!. 12 (1847), 497-320, исследовал действенность этого метода,] (Ь) Так же, как и в упр. 22, можно положить, что и = пм .. п„где все и, = 1+ 2~'9,— различные простые числа и й~ < < й,; положим также, что бсб(п — 1, и; — Ц = 2 '4,'. Будем называть число х плохим, еслп оно приводит к ошибочной классификации числа и как похожего на простое. Пусть П„= 11;., д,'2ьешыл Π— число решений уравнения хы О!з = 1. Количество плохих чисел к, для которых выполняется равенство („-*) = 1, равно П„, умноженному на дополнительный множитель — при й~ < й, (Этот множитель з 1 необходим, чтобы гарантировать выполнение равенства ( — „* ) = -1 для четного количества чисел и, прн й; < Ь.) Количество плохих чисел х, для которых (к) = -1, равно П„, если й~ = й, и 0 в противном случае. (Если выполняется условие яы" Нш ш -1 (по модулю н,), то получим в результате ( ~ ) = -1 при Й, = Й, (-„~;) = +1 и Ь» > Ь и противоречие, если Ь; < й.
Если Й» = Й, то существуют нечетные количества чисел Ьо равных й.] Замечание. Вероятность того, что выбор плохой, будет >» только тогда, когда и— число Кармайкла, для кото1юго Ь, < Ь; например, я = 7 13 19 = 1729, число, ставшее известным благодаря Рамануджаиу (Кюпапа)ап) в другом контексте. Этот анализ был продолжен Луисом Моньером (1ошэ Ыопюг) при получении следующих формул в замкнутом виде для количества плохих чисел х в общем случае: Ь'„~ 5„абеб( —, и, — 1). Здесь Ь'„— количество плохих чисел к в этом упражнении, а Ю„равно либо 2 (если Ь» = Ь), либо 1э (если й; < Ь и ею является нечетным для некоторого»), либо 1 (в остальных случаях). (с) Если яе шпаг» = 1, то 1 = ('— ) = (-„')э = (-*„).
Если х э ш -1 (по модул»о и). то порядок х по модулю ьп должен быть нечетным кратным числа 2»+' для всех простых делителей»ь числа и. Пусть и = и",... и'„' и ц; = 1 + 2»~'д,'; тогда ( — „' ) = ( — 1)г', так что (-*) = +1 или — 1 в зависимости от того, какой будет Я е»9,' — четной или нечетной. Поскольку и ш (1+ 2»+» '] е»9,') (по модулю 2»+~), сумма Яе 4, 'будет нечетной тогда и только тогда, когда у + 1 = Й. (ТЬеогейса! Сошр. Яс»! 12 (1980), 97.108.] 24. Пусть 5»» — матрица, имеющая по одной строке на каждое нечетное непростое число и в интервале 1 < и < Ь», и А» — 1 столбцов, пронумерованных от 2 до Х.
Значение элемента, расположенного в строке и и столбце з, равно 1, если проверка числа и алгоритмом Р посредством к дает отрицательный результат, и равно 0 а ос»альных случаях. Известно. что если Л» = 9п + г и О < г < и, то и строке и содержится не более -1 + д(Ь + 1) + ппп(Ь, + 1, г) < дЦ(п — 1)+1)+пцп(Ь +1, г) < 1дп+пип(1п, г) = зй Ьпип(ьп — 1г, 1з ) < 1А»+-'и < -'А» элементов, равных 0; поэтому по меньшей мере половина элементов матрицы равна 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
