Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 225
Текст из файла (страница 225)
Во время каждой итерации цикла зтййе в строке 7 используется рекуррентное соотношение хз = (хе, — 1) пюс1 и (31.43) Часть ИЬ Изарамные темы позволяющее получить очередное значение х; бесконечной последовательности (31.44) Х1, Х2, ХЗ, Х4,... а значение индекса 1 увеличивается в строке 6. Несмотря на то что для простоты восприятия в коде используются значения переменных с индексами хо программа работает точно так же, если опустить все и~лексы, поскольку при каждой итерации необходимо поддерживать только одно последнее значение хь С учетом этой модификации в процедуре используется лишь фиксированное количество ячеек памяти. Время от времени программа сохраняет последние из сгенерированных значений хе в переменной у.
Сохраняются те значения, индексы которых равны степени двойки: Х1 Х2 Х4~ХЗ,Х16~' ' В строке 3 сохраняется значение х1, а в строке 12 сохраняется хы когда 1 становится равным )с. Переменная Е инициализируется двойкой в строке 4, а строка 13 удваивает ее, когда в строке 12 происходит обновление у.
Так что /с пробегает значения 1, 2, 4, 8,... и всегда дает индекс очередного значения хы которое будет сохранено в переменной у. В строках 8-10 предпринимается попытка разложить число и с помощью сохраненного значения у и текущего значения хь В частности, в строке 8 вычисляется наибольший общий делитель д = йсс((у — хз, п). Если значение переменной д — нетривиальный делитель числа и (это проверяется в строке 9), то оно выводится в строке 1О.
Эта процедура поиска делителей на первый взгляд может показаться несколько загадочной. Однако заметим, что она никогда не выдает неверного ответа; все числа, которые выводит процедура Ро1.1.лкп-йно, являются нетривиальными делителями п.
Тем не менее эта процедура может вообще не выводить никаких данных; нет никакой гарантии, что она выдаст хоть какой-то результат. Тем не менее, как мы сможем убедиться, есть веская причина ожидать, что процедура Р01.1.якп-кно выведет множитель р числа и после 9( /р) итераций цикла ьчьйе. Таким образом, если и — составное число, то эта процедура после приблизительно п114 обновлений обнаружит достаточное количество делителей, чтобы можно было полностью разложить число и, поскольку все простые множители р числа и, кроме, возможно, наибольшего, меньше ~/й. Начнем анализ поведения представленной выше процедуры с изучения вопроса о том, сколько времени должно пройти, пока в случайной последовательности по модулю и не повторится значение.
Поскольку множество ят конечное и поскольку каждое значение последовательности (31.44) зависит только от предыдущего, то эта последовательность в конце концов начнет повторяться. Достигнув некоторого значения х„такого, что при некотором 4 < 1 выполняется равенство хз = х, последовательность зациклится, поскольку х;~1 = хз ь1, хейг = хз+г и т.д. Понять, почему этот метод был назван эвристическим р-методом, помогает рис. 31.7. Часть последовательности х1,хг,..., х 1 можно изобразить в виде "хвоста" греческой буквы р, а цикл х.,х 4.1,...,х, — в виде "тела" этой буквы.
Глава 38 уеоретияо-числоаые алгарнльим 998 ЗЮ 814 596 хг !77 хв 1186 1~ ]20 хт /" ~ хяз тгЗ. аз зз ,8: хэ 1194 339 529 ~7) ,.]б 8 хг ::з х] 2 х] ]зэ пюд 19 юсд 1587 пюд 75 га] гв] ге] Рассмотрим вопрос о том, насколько длинной должна быль последовательность значений хг, чтобы начать повторяться. Это не совсем то, что нам нужно, но вскоре станет понятно, как модифицировать зти рассуждения.
Чтобы оценить зто время, будем считать, что функция уп(х) = (х — 1) пзог(п ведет себя, как "случайная" функция. Конечно, на самом деле она не случайная, но зто предположение соп]асуется с наблюдаемым поведением процедуры Рошап-Кн(). Далее предположим, что каждое значение хг извлекается независимым образом из множеспщ Ж„и что все они распределены в этом множестве равномерно. В соответствии с анализом парадокса о днях рождения, проведенном Рис. 31.7.
р-эврисгика Поллараа. (а) Значениа, полученные с помощью рекуррентного соотношения х,4] = (тз — 1) щог) 1387, начиная с хг = 2. Разложение числа 1387 на простые мнозппели имеет вид 19 73. Толстые стрелки указывают итерации, выполненные до нююждения мн]лкителя 19. Стрелки, изображенные тонкими линиями, указывают на те значения в итерации, которые так и не достигаются. С ик помощью иллкктрируется форма буквы р. Серым фоном выделены те значения, которые сохраняются процедурой Роььлко-Нно в переменной р. Множитель 19 обнаруживается при достижении значения хг = 177, кос!а вычисляется величина бс])(63 — 177, 1387) = 19.
Первое значение х, жпорое впоследствии повторится, равно 1186, ццнако множитель 19 обнаруживаетса еще до этого повтора (б) Значения, полученные с помощью того же рекуррентного соотношения, по модулю 19. Каящое значение хг из части (а) эквивалентно по модулю 19 значению х';„показанному в этой чжти. Нвпример, и хз = 63, и хг = 177 эквивалентны б по модулю 19.
(в) Значения, полученные с помощью того же рекуррентного соотношения, по модулю ТЬ. Каждое значение хг из части (а) эквивалентно по модулю 73 значению х,", показанному в этой части. Согласно китайской теореме об остатках каждый узел в части (а) соответствует паре узлов — одному из части (6) и одному из чжтн (в). Часть Г11 Иэаранныетены х, = х; шос( р э для всех э.
Кроме того, поскольку в определении функции /„ содержатся только арифметические операции (возведение в квадрат и вычитание) по модулю и, нетрудно показать, что величину х',ь, можно вычислить на основании величины х,'. Рассмотрение последовательности "по модулю р" — сокращенная версия того, что происходит по модулю и: ! хэ+ 1 х,ьг шос( р 1„(х,) шосг р ((х, — 1) шос( и) шос1 р (х, — 1) шос( р ((х, пюс1 р) — 1) эпос( р ((х,) — 1) шос) р 1р(х;) .
(согласно упр. 31.1.7) Таким образом, хотя мы и не вычислили явным образом последовательность (х',), она вполне определена и подчиняется тому же рекуррентному соотношению, что и последовательность (х;). Продолжая рассуждать так же, как и ранее, можно прийти к выводу, что математическое ожидание количества шагов„выполненных перед тем, как повторится последовательность (х',), равно 9( /р). Если значение р малб по сравнению с и, последовательность (х',) может начать повторяться намного быстрее, чем последовательность (х,).
Действительно, как демонстрируют части (б) и (в) рис. 31.7, последовательность (х',) начнет повторяться, как только два элемента последовательности (х;) окажутся эквивалентными по модулю р, а не по модулю и. Обозначим через 1 индекс первого повторившегося значения последовательности (х',), а через и > Π— длину цикла, полученного таким образом. Другими словами, 1 и и > Π— наименьшие значения, для которых при всех э > О выполняется равенство х',, = х', „,. Согласно приведенным выше рассуждениям, математическое ожидание как величины 1, так и и равно й( /р). Заметим, что если х',, = х', „,,тор ) (хе+а+с — хсч,).
Таким образом, ясс((хэ.ьн.~,— хэчыи) > 1. Поэтому после того как в процедуре Рогл.лкп-йно в переменной у будет сохранено любое значение хы такое, что )с > 1, величина у шос( р всегда будет в разделе 5.4.1, математическое ожидание количества шагов перед зацикливанием последовательности равно й(т/й). Теперь перейдем к требуемой модификации. Пусть р — нетривиальный множитель числа и, такой, что кос)(р,и/р) = 1.
Например, если разложение числа и имеет вид и = р~'р~э р,", то в качестве множителя р можно выбрать величину р~э. (Полезно запомнить, что если еэ = 1, то роль р будет играть наименьший простой множитель числа и.) Последовательность (хс) порождает соответствукицую последовательность (х',) по модулю р, где 1цс5 Глава 3! Теоретино-чиеловые алгориосиы находиться в цикле по модулю р. (Если в переменной у будет сохранено новое значение, оно также окажется в цикле по модулю р.) В конце концов переменной и будет присвоено значение, превышающее и, после чего в процедуре будет пройден полный цикл по модулю р, не сопровождающийся изменением значения д.
Множитель числа и будет обнаружен тогда, когда яч "натолкнется" на ранее сохраненное значение у по модулю р, т.е. когда х, = у (шов( р). Скорее всего, найденный множитель будет равен р, хотя случайно это может оказаться число, кратное р. Поскольку математическое ожидание величин 1 и и равно Н( 7р), математическое ожидание количества шагов, необходимых для получения множителя р, равно еЭ( Гр).
Есть две причины, по которым этот алгоритм может оказаться не таким быстрым, как ожидается. Во-первых, проведенный выше эвристический анализ времени работы нестрогий, и цикл значений по модулю р может оказаться намного длиннее, чем /р. В этом случае алгоритм работает правильно, но намного медленнее, чем хотелось бы. Практически же это представляется сомнительным. Вовторых, среди делителей числа и, которые выдаются этим алгоритмом, всегда может оказаться один из тривиальных множителей 1 или и. Например, предположим, что п = рд, где р и д — простые числа. Может оказаться, что значения г и и для множителя р идентичны значениям г и и для множителя д, и поэтому множитель р будет всегда обнаруживаться в результате выполнения той же операции ясг(, в которой обнаруживается множитель 9. Поскольку оба множителя находятся одновременно, процедура выдает тривиальный множитель рд = п, который бесполезен.
На практике и эта проблема кажется несущественной. При необходимости нашу эвристическую процедуру можно перезапустить с другим рекуррентным соотношением вида х,еэ = (х~ — с) шо4( п. (Значений с = 0 и с = 2 следует избегать по причинам, вникать в которые мы здесь не станем; но другие значения вполне подходят.) Конечно же, этот анализ эвристический и нестрогий, поскольку рекуррентное соотношение на самом деле не является "случайным". Тем не менее на практике процедура работает хорошо„ и, по-видимому, ее эффективность совпадает с полученной в ходе эвристического анализа.
Она представляет собой вероятностный метод поиска небольших простых множителей, на которые раскладывается большое число. Все, что нужно для полного разложения )7-битового составного числа и, — найти все его простые множители, меньшие (и~7 ~), поэтому можно ожидать, что процедуре Роылкгг-Кно понадобится не более пэ74 = 2014 арифметических операций и не более и'14~3з = 20~4)ЗЭ битовых операций.
Зачастую наиболее привлекательной особенностью этой процедуры оказывается ее способность находить небольшой множитель р числа и ценой ожидаемого количества Й( /р) арифметических операций. Упражнения 31.9.1 Когда процедура Роь1.лкп-йцо выведет множитель 73 числа 1387, если история вычислений в ней имеет вид, показанный на рис. 31.7, (а)? ЭЭ Эви.
Э724 10зб Часть еП. Избранные темы 31.9.2 Предположим, что задана функция /: К„-+ г.„и начальное значение хо е Ж„. Определим рекуррентное соотношение х; = У(хз з) для 1 = 1,2,.... Пусть 1 и и > 0 — наименьшие значения, такие, что хе~; — — хзо„ь, для 1 = О, 1,... (в терминах р-алгоритма Полларда 1 — зто длина хвоста, а и — длина цикла р). Сформулируйте эффективный алгоритм, позволяющий точно определить значения 1 и и, и проанализируйте время его работы. 31.9.3 Чему равно математическое ожидание количества шагов, которые понадобится выполнить процедуре Роь1.лно-йно, чтобы обнаружить множитель вида р', где р — простое число, а е > 1? 31.9.4 * Как уже упоминалось, одним из недостатков процедуры Роь1.лко-йно является то, что на каждом шаге рекурсии в ней необходимо выполнять операцию ясс).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
