Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 206
Текст из файла (страница 206)
Поскольку пз'" = — 1 (шос(и), из следствия 31.29 из китайской теоремы об остатках вытекает„что пз" ш = — 1(шос1иг). Согласно следствию 31.28, существует значение со, которое одновременно удовлетворяет таким уравнениям: и = и (гпос1пг), со = 1(шос1пз). Глава 31. Теоретико-числовые алгоритмы 1005 Поэтому се~ "= — 1 (пюс(п1), иР "= 1(пюс1из). Согласно следствию 31.29, из соотношения саз " ф1 (пюс(пг) следует, что саз'" ф ф1(пюс1п), а из соотношения се~'" ~ — 1(шос)пз) — что са~'" ф'= — 1(пюс1п). Таким образом, иР'" ф ~ 1 (пюс1п), поэтому са ф В.
Остается показать, что са е 2;,. Для этого построим рассуждения отдельно по модулю п1 и по модулю из. Что касается операций по модулю пм заметим, что поскольку о Е У„', справедливо равенство 8сс)(и,п) = 1, так что и 8сс((о,п1) = 1; если у числа е нет общих делителей с п, то у него также нет общих делителей с пп Поскольку са ив з е(пюс1п1), можно сделать вывод, что 8сс1(щ,п1) = 1.
Что же касается операций по модулю пз, заметим, что из соотношения и = 1 (шос1из) следует, что 8сс1 (са, пз) = 1. Для того чтобы объединить эти результаты, воспользуемся теоремой 31.6, из которой следует, что 8сс1(ю,и|из) = бсс1(са,и) = 1, т.е. и Е Х;,.
Следовательно, ю ЕЕ„'-В, и мы приходим к выводу, что в случае 2 В является истинной подгруппой 2„'. Итак, мы убедились, что в обоих случаях количество свидетельств того, что число п — составное, не меньше (п — 1)/2. И Теорема 31.39. При любом нечетном п ) 2 и положительном целом в вероятность того, что процедура Мцл.нн КАвпч(п, в) выдаст неправильный результат, не превышает 2 '. Доказансыьснсво. Из теоремы 31.38 следует, что если п — составное, то при каждом выполнении цикла 1ог в строках 1-4, вероятность обнаружить свидетельство х того, что и — составное, не меньше 1/2.
Процедура Мшьнк Клинч допускает ошибку только в том случае, когда ей не удалось обнаружить такое свидетельство в каждой из в итераций основного цикла. Вероятность подобной последовательности неудач не превышает 2 '. й Таким образом, если выбрать в = 50, то этого должно хватить почти для любого приложения, какое только можно себе представить. Если поиск больших простых чисел производится путем применения процедуры Мп.енк КАнлч к случайно выбранным большим целым числам, то можно показать (хотя мы не станем здесь этого делать), что выбор небольшого значения в (скажем, 3) с очень малой вероятностью приведет к ошибочным результатам. Другими словами, для случайным образом выбранного нечетного составного целого числа п математическое ожидание количества значений оснований, не являющихся свидетельствами того, 1006 Часть ЧП.
Избранные темы что и — составное, с большой вероятностью намного меньше (и — 1)/2. Однако если число п выбирается не случайным образом, самое лучшее, что можно доказать с помощью улучшенной версии теоремы 31.38, — что количество значений оснований, не являющихся свидетельствами, не превышает (и — 1)/4.
Более того, существуют такие целые числа п, для которых это количество равно (и — 1)/4. Упражнения 31.8-1. Докажите, что если целое нечетное число и > 1 не является простым числом или степенью простого числа, то существует нетривиальный квадратный корень из 1 по модулю и. * 31.8-2. Теорему Эйлера можно слегка усилить, придав ей такой вид: а 00 се 1(шос1п) для всех аЕ Щ, где п = р"р" р~", а функция Л (и) определена как Л(п) = 1ст(ф(рг~'),...,ф(р~')) .
(31.40) Докажите, что Л(и) ~ ф(п). Составное число п является числом Кармайкла, если Л (и) ~ и — 1. Наименьшее из чисел Кармайкла равно 661 = = 3 11 17; при этом Л(п) = 1сш(2,10,16) = 80, а это делитель 560. Докажите, что числа Кармайкла должны быть "свободными от квадратов" (т.е. не делиться на квадрат ни одного простого числа) и в то же время представлять собой произведение не менее трех простых чисел.
По этой причине они встречаются не очень часто. 31.8-3. Докажите, что если х — нетривиальный квадратный корень из единицы по модулю и, то и бсг1 (х — 1, и), и бсс1 (х + 1, и) являются нетривиальными делителями и. * 31.9 Целочисленное разложение Предположим, задано целое число и, которое нужно разложить (Гас1ог) на простые множители. Тест простоты, представленный в предыдущем разделе, может дать информацию о том, что число п — составное„однако он обычно не выводит его простых множителей. Разложение больших целых чисел п представляется намного более сложной задачей, чем определение того, является ли число п простым или составным.
Располагая суперкомпьютерами и наилучшими на сегодняшний день алгоритмами, нереально разложить произвольное 1024-битовое число. Глава 31. Теоретико-числовые алгоритмы 1007 Эвристический р-метод Полларда РОы.Акп Кно(п) 1 з — 1 2 х1 < — КАХООМ(0, и — 1) 3 у — х1 4 й -2 5 иЫ1е ТЛЕ 6 де( -1+1 7 х; — (хз — 1) щог) п 8 г( — бсг1(у — х;, п) 9 Идф1идфп 10 1йеп рппг г( 11 Ыг=й 12 гйепу -х; 13 7с — 27г Опишем работу этой процедуры. В строках 1-2 переменной 1 присваивается начальное значение 1, а переменной х1 — случайное значение из Е„. Итерации цикла и Ьйе, который начинается в строке 5, продолжаются до бесконечности в поисках множителей числа п.
При каждой итерации этого цикла в строке 7 используется рекуррентное соотношение х; — (хз, — 1) щодп, (31.41) позволяющее получить очередное значение х; бесконечной последовательности (31.42) хмхз, хз,..., а соответствующее значение индекса 1 увеличивается в строке 6. Несмотря на то, что для простоты восприятия в коде используются значения переменных с индексами х;, программа работает точно так же, если мы опустим все индексы, Пробное деление на каждое целое число вплоть до В гарантирует, что будет полностью разложено любое число вплоть до Вз. Представленная ниже процедура позволяет разложить любое число вплоть до В4 (еслн мы не окажемся неудачниками), выполнив тот же объем работы. Поскольку эта процедура носит лишь эвристический характер, ничего нельзя утверждать наверняка ни о времени ее работы, ни о том, что она действительно достигнет успеха.
Несмотря на это„ данная процедура оказывается очень эффективной на практике. Другое преимущество процедуры РОгл.Аап КнО состоит в том„что в ней используется лишь фиксированное количество памяти. (Для небольших чисел ее легко реализовать даже на программируемом калькуляторе.) 1008 Часть ЧП. Избранные темы поскольку при каждой итерации необходимо поддерживать толью одно последнее значение х;. С учетом этой модификации в процедуре используется лишь фиксированное количество ячеек памяти.
Время от времени программа сохраняет самые последние из сгенерированных значений х; в переменной у. Сохраняются те значения, индексы которых равны степени двойки: хз, хз, х4, ха, х16,... В строке 3 сохраняется величина хп а в строке 12 — величины хы когда 1 становится равным к. В строке 4 переменной 1с присваивается начальное значение 2, а строке 13 эта переменная удваивается при каждом обновлении значения переменной у. Поэтому переменная к пробегает значения 1,2,4,8,..., каждое из юторых используется в качестве индекса очередной величины хы сохраняемой в переменной у. В строках 8-10 предпринимается попытка разложить число и с помощью сохраненного значения у и текущего значения х;.
В частности, в строке 8 вычисляется наибольший общий делитель Н = 8сг1 (у — х;, и). Если значение переменной д — нетривиальный делитель числа и (это проверяется в строке 9), то оно выводится в строке 1О. Возможно, эта процедура поиска делителей на первый взгляд может показаться несколько загадочной.
Однако заметим, что она никогда не выдает неверного ответа; все числа, которые выводит процедура Роььлкп Кно, являются нетривиальными делителями и. Тем не менее, эта процедура может вообще не выводить никаких данных; совершенно нет уверенности в том, что она даст хоть какой-то результат. Тем не менее, как мы сможем убедиться, есть веская причина ожидать, что процедура РОььАкп КнО выведет множитель р числа и после 6 ( /р) итераций цикла и Ы!е. Таким образом, если и — составное число, то эта процедура после приблизительно и~/4 обновлений обнаружит достаточное количество делителей, чтобы можно было полностью разложить число и, поскольку все простые множители р числа и, кроме, возможно, последнего, меньше ~/й. Начнем анализ поведения представленной выше процедуры с того, что исследуем, сколько времени должно пройти, пока в случайной последовательности по модулю и не повторится значение.
Поскольку множество 2„ конечное, и посюльку каждое значение последовательности (31.42) зависит только от предыдущего, то эта последовательность в конце концов начнет повторяться. Достигнув неюторого значения х,, такого что при некотором 1 < з выполняется равенство х; = х, последовательность зациклится, поскольку х;+з = х +ы х;+з = х.+з и т.д.
Понять, почему этот метод был назван "эвристическим р-методом*', помогает рис. 31.3. Часть последовательности хз,хз,...,х з можно изобразить в виде "хвоста" греческой буквы р, а цикл х,х ~.ы ...,х, — в виде "тела" этой буквы. На рис. 31.3а приведены значения, полученные из рекуррентного соотношения Часть ЧП. Избранные темы 1010 Рассмотрим вопрос о том, сколько времени понадобится последовательности значений х;, чтобы она начала повторяться.
Это не совсем то, что нам нужно, но вскоре станет понятно, как модифицировать этот параметр. Чтобы оценить это время, будем считать, что функция У„(х) = (х — 1) шос1 и ведет себя как "случайная'* функция. Конечно, на самом деле она не случайная, но это предположение согласуется с наблюдаемым поведением процедуры РО~.АкО КнО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
