Алгоритмы - построение и анализ (1021735), страница 207
Текст из файла (страница 207)
Сохраняются те значения, индексы которых равны степени двойки: хз, хз, х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 и ведет себя как "случайная'* функция. Конечно, на самом деле она не случайная, но это предположение согласуется с наблюдаемым поведением процедуры РО~.АкО КнО. Далее, предположим, что каждое значение х; извлекается независимым образом из множества 2„, и что все они распределены в этом множестве равномерно. В соответствии с анализом парадокса о днях рождения, проведенном в разделе 5.4.1, математическое ожидание количества шагов, предпринятых перед зацикливанием последовательности, равно 9 (~/й).
Теперь перейдем к требуемой модификации. Пусть р — нетривиальный множитель числа и, для которого справедливо уравнение ясс1 (р, и/р) = 1. Например, если разложение числа и имеет вид и = р" р" . р',", то в качестве множителя р можно выбрать величину р". (Если е1 = 1, то толь р будет играть наименьший простой множитель числа и; это полезно взять на заметку.) Последовательность (хс) порождает соответствующую последовательность (х',) по модулю р, где х', = х, пюс1 р для всех г.
Кроме того, поскольку в определении функции г„содержатся только арифметические операции (возведение в квадрат и вычитание) по модулю и, нетрудно показать, что величину х';+1 можно вычислить на основании величины х';. Рассмотрение последовательности "по модулю р" — уменьшенная версия того, что происходит по модулю и: ! хс+с — — х,+1 пюс1 р = У„(хс) пюс1 р = ((х~ — 1) шос1и) тпос1 р = (х~ — 1) тпос1 р = ((хс пюс1 р) — 1) шос1 р = ~(х';) — 1) тос1 р = Ь( с) где четвертое равенство следует из упражнения 31.1-6.
Таким образом, хотя мы и не вычислили явным образом последовательность (х,'), эта последовательность вполне определена и подчиняется тому же рекуррентному соотношению, что и последовательность (х;). Глава 31. Теоретико-числовые алгоритмы 1011 Рассуждая так, как и ранее, момсно прийти к выводу, что математическое ожидание количества шагов, выполненных перед зацикливанием последовательности (х',), равно Э ( сгр).
Если значение р мало по сравнению с п, то последовательность (х',) может начать повторяться намного быстрее, чем последовательность (х,). В самом деле, последовательность (х';) начнет повторяться, как только два элемента последовательности (хс) окажутся эквивалентными по модулю р, а не по модулю и. Вышесказанное проиллюстрировано на рис.
31.3б и в. Обозначим через 1 индекс первого повторившегося значения последовательности (х',), а через и > Π— длину цикла, полученного таким образом. Другими словами, 1 и и > Π— наименьшие значения, для которых при всех 1 > О выполняется равенство х'+, — — х',+„+,. Согласно приведенным выше рассуждениям, математическое ожидание величин 8 и и равно 9 ( /р). Заметим, что если х',+, —— = х',+„+,, то р ~ (хн.„+с — хс+,). Таким образом, ксс1 (хс+„а; — хс+;, и) > 1. Поэтому после того как в процедуре Роьс.Ако Кно в переменной у будет сохранено любое значение хы у которого сс > т, величина у спос1 р всегда будет находиться в цикле по модулю р.
(Если в переменной у будет сохранено новое значение, оно также окажется в цикле по модулю р.) В конце концов переменной к будет присвоено значение, превышающее и, после чего в процедуре будет пройден полный цикл по модулю р, не сопровождающийся изменением значения у. Множитель числа п будет обнаружен тогда, когда х, "натолкнется" на ранее сохраненное значение у по модулю р, т.е. когда х; = у (пюс1р). Скорее всего, найденный мнохситель будет равен р, хотя это случайно может оказаться число, кратное р.
Поскольку математическое ожидание величин с и и равно О ( /р), математическое ожидание количества шагов, необходимых для получения множителя р, равно 9 (,/р). Есть две причины, по которым этот алгоритм может оказаться не таким эффективным, как ожидается.
Во-первых, проведенный выше эвристический анализ времени работы нестрогий, и цикл значений по модулю р может оказаться намного длиннее, чем /р. В этом случае алгоритм работает правильно, но намного медленнее, чем хотелось бы. Практически же это представляется сомнительным. Во-вторых, среди делителей числа и, которые выдаются этим алгоритмом, всегда может оказаться один из тривиальных множителей 1 или п. Например, предположим, что п = рс1, где р и в — простые числа. Может оказаться, что значения т и и для множителя р идентичны значениям т и и для множителя д, и поэтому множитель р будет всегда обнаруживаться в результате выполнения той же операции ясс1, в которой обнаруживается множитель сг.
Поскольку оба множителя находятся одновременно, процедура выдает тривиальный множитель рс1 = п, который бесполезен. На практике и эта проблема кажется несущественной. При необходимости нашу эвристическую процедуру можно перезапустить с другим рекуррентным соотношением, которое имеет вид хс+с — (х1 — с) (пюс1п).
(Значений параметра 1012 Часть т'11. Избранные темы с, равных О и 2, следует избегать по причинам, вникать в которые мы здесь не станем; другие значения вполне подходят.) Конечно же, этот анализ нестрогий и эвристический, поскольку рекуррентное соотношение на самом деле не является "случайным". Тем не менее, на практике процедура работает хорошо, и, по-видимому, ее эффективность совпадает с полученной в ходе эвристического анализа. Она представляет собой вероятностный метод поиска небольших простых множителей, на которые раскладывается большое число.
Все, что нужно для полного разложения 13-битового составного числа и, — найти все его простые множители, меньшие 1п1~з~, поэтому можно ожидать, что процедуре Ро~ьАкп Кно понадобится не более из/4 = 2д/4 арифметических операций и не более п1~413з = 2Д/413з битовых операций. Зачастую наиболее привлекательной особенностью этой процедуры оказывается ее способность находить небольшой множитель р числа п, выполнив при этом операции, математическое ожидание количества которых равно 8 ( /р). Упражнения 31.9-1. Когда процедура Роымип Кно выведет множитель 73 числа 1387, если история вычислений в ней имеет вид, показанный на рис. 31.3а? 31.9-2.
Пусть задана функция Г': Е„- Е„и начальное значение хо е Е„. Определим рекуррентное соотношение яч = г'(х; 1) для 1 = 1, 2,.... Пусть 1 и и > Π— наименьшие значения, для которых выполняется уравнение хс+; — — хс+„+; для 1 = 1, 2,... (в терминах р-алгоритма Полларда, 1 — это длина хвоста, а и — длина цикла р). Сформулируйте эффективный алгоритм, позволяющий точно определить значения 1 и и, и проанализируйте время его работы. 31.9-3. Чему равно математическое ожидание количества шагов, которые понадобится выполнить процедуре Роь1.Апп Кно, чтобы обнаружить множитель вида р', где р — простое число, а е > 1? * 31.9-4.
Как уже упоминалось, одним из недостатков процедуры Роы.лиз Кно является то, что на каждом шаге рекурсии в ней необходимо выполнять операцию йод. Было высказано предположение, что вычисления йод можно объединить, накопив произведение нескольких величин х, и используя это произведение при вычислении кос) вместо величины х;. Приведите подробное описание того, как можно было бы реализовать эту идею, почему она работает и какой размер группы можно было бы выбрать для достижения максимального эффекта при обработке б-битового числа и. Глава 31. Теоретико-числовые алгоритмы 1013 Задачи 31-1. Бинарный алгоритм ясб На большинстве компьютеров операции вычитания, проверки четности (нечетное или четное) и деления пополам выполняется быстрее, чем вычисление остатка.
В этой задаче исследуется бинарный алгоритм йсй (Ьшагу ясд а!яопйп~), позволяющий избежать вычисления остатков, которые используются в алгоритме Евклида. а) Докажите, что если числа а и 6 — четные, то справедливо уравнение ясс! (а, 6) = 2 ясй (а/2, 6/2). б) Докажите, что если а — нечетное, а 6 — четное, то справедливо уравнение ясс! (а, Ь) = ясс1 (а, Ь/2). в) Докажите, что если числа а н Ь вЂ” нечетные, то справедливо уравнение ась(а,Ь) = ясд((а — 6)/2,6). г) Разработайте эффективный бинарный алгоритм поиска ясс1 для целых чисел а и Ь, где а > 6, время работы которого равно О (1яа). Предполагается, что на каждое вычитание, проверку на четность и деление пополам затрачивается единичный интервал времени.
31-2. Анализ битовых операций в алгоритме Евклида а) Рассмотрим обычный алгоритм деления "на бумаге" а на 6, в результате которого получается частное о и остаток т. Покажите, что в этом методе требуется выполнить О ((1+ !я о) 1я 6) битовых операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
