Алгоритмы - построение и анализ (1021735), страница 208
Текст из файла (страница 208)
б) Определим функцию а(а,Ь) = (1+ 1яа) (1+1яЬ). Покажите, что количество битовых операций, которые выполняются в алгоритме Епсыгз при сведении задачи вычисления величины ясб(а,6) к вычислению величины ясс! (Ь, а пюс1 Ь), не превышает с(р (а, 6)— -р (6, а шод 6) ) для некоторой достаточно большой константы с > О. в) Покажите, что выполнение алгоритма Е1к!.нз(а, 6) требует в общем случае О (р (а, 6)) битовых операций, и О (,9з) битовых операций, если оба входных значения являются !3-битовыми числами.
31-3. Три алгоритма вычисления чисел Фибоначчи В этой задаче производится сравнение производительности работы трех методов вычисления и-го числа Фибоначчи Г„при заданном и. Считаем, что стоимость сложения, вычитания или умножения двух чисел независимо от их размера равна О (1). Часть Ч11.
Избранные темы 1014 а) Покажите, что время работы прямого рекурсивного метода вычисления числа Р'„на основе рекуррентного соотношения (3.21) увеличивается экспоненциально с ростом п. б) Покажите, как с помощью запоминания вычислить число Г„за время 0(п). в) Покажите, как вычислить число Р'„за время 0(1йп), используя только сложения и умножения целых чисел. (Указание: рассмотрите матрицу и ее степени.) г) Теперь предположим, что для сложения двух Д-бнтовых чисел требуется время 6 (13), а для их умножения — время 9 (Дз). Чему равно время работы перечисленных выше алгоритмов с учетом такой стоимости выполнения элементарных арифметических операций? 31-4. Квадратичные вычеты Пусть р — нечетное целое число.
Число а Е Е' является квадратичр ным вычеииии (Чпадгайс гезЫпе), если уравнение хз = а(тасар) имеет решение относительно неизвестного х. а) Покажите, что существует ровно (р — 1)/2 квадратичных вычета по модулю р. б) Если число р — простое, то определим симван Лежандра (1.еяепйе зушЬо1) ® для ае Ер, как равный 1, если а — квадратичный вычет по модулю р, и -1 в противном случае.
Докажите, что если а 6 Ер, то = а(Р 1~ (шос1р). р/ Разработайте эффективный алгоритм, позволяющий определить, является ли заданное число а квадратичным вычетом по модулю р. Проанализируйте время работы этого алгоритма. в) Докажите, что если р — простое число вида 4(с + 3, а а — квадратичный вычет в Ер, то величина а"+' шос1 р равна квадратному корню а по модулю р. Сколько времени понадобится для поиска квадратного корня квадратичного вычета а по модулю р? г) Разработайте эффективный рандомизированный алгоритм поиска неквадратичного вычета по модулю, равному произвольному простому числу р.
Другими словами, нужно найти элемент Ер, который Глава 31. Теоретико-числовые алгоритмы 1015 не является квадратичным вычетом. Сколько в среднем операций понадобится выполнить этому алгоритму? Заключительные замечания Книга Нивена (Ы1теп) и Цукермана (Еис1сеппап) [231] содержит прекрасное введение в элементарную теорию чисел. У Кнута (КпигЬ) [183] приведено подробное обсуждение алгоритмов, предназначенных для поиска наибольших общих делителей, а также других основных теоретико-числовых алгоритмов. Бэтч (Ва1сЬ) [28] и Ризель (К(езе1) [258] представили более современный обзор вычислительных приложений теории чисел.
В статье Диксона (Бйхоп) [78] приведен обзор методов разложения и проверки простоты чисел. В трудах конференции под редакцией Померанца (Ротегапсе) [245] содержится несколько превосходных обзорных статей. Позже Бэтч и Шаллит (БЬа!йг) [29] представили прекрасный обзор основных вычислительных приложений теории чисел.
В книге Кнута [183] обсуждается история возникновения алгоритма Евклида. Он встречается в трактате "Начала" греческого математика Евклида, опубликованном в 300 году до н.э., в седьмой книге в теоремах 1 и 2. Описанный Евклидом алгоритм мог быть получен из алгоритма, предложенного Евдоксом около 375 года до н.э. Не исключено, что алгоритм Евклида является старейшим нетривиальным алгоритмом; соперничать с ним может только алгоритм умножения, известный еще древним египтянам. В статье Шаллита [274] описана история анализа алгоритма Евклида. Авторство частного случая китайской теоремы об остатках (теорема 31.27) Кнут приписывает китайскому математику Сунь-Цзы, который жил приблизительно между 200 г.
до н.э. и 200 г. н.э., — дата довольно неопределенная. Тот же частный случай сформулирован греческим математиком Никомахусом (Ы1сЬошасЬиз) около 100 г. н.э. В 1247 году он был обобщен Чином Чиу-Шао (СЬЬ1п СЬ(п-БЬао). Наконец, в 1734 году Л. Эйлер (1.. Еи!ег) сформулировал и доказал китайскую теорему об остатках в общем виде. Представленный в этой книге рандомизированный алгоритм проверки простоты чисел взят из статей Миллера (М111ег) [221] и Рабина (КаЬ1п) [254]; это самый быстрый (с точностью до постоянного множителя) из известных рандомизированных алгоритмов проверки простоты. Доказательство теоремы 31.39 слегка адаптировано по сравнению с тем, что было предложено Монье (Могйег) [224, 225]. Рандомизация представляется необходимой для того, чтобы получить алгоритм проверки простоты, время работы которого выражалось бы полиномиальной функцией.
Самый быстрый из известных детерминистических алгоритмов этого вида— версия Кохена-Ленстры (СоЬеп-Ьепзпа) [65] теста на простоту, предложенного Адлеманом (Ад!ешао), Померанцом и Раминли (Кщпеп1у) [3]. Проверяя простоту 1016 Часть ЧП. Избранные темы числа и длиной [18 (и + 1)], он затрачивает время (18 и) ( я я я "1, лишь немного превышающее полиномиальное.
Обстоятельное обсуждение задачи поиска больших "случайных" простых чисел содержится в статье Бьючимина (Веапспещ1п), Брассарда (Вгаззагб), Крипо (Сгереап), Готье (Ооийег) и Померанца [33]. Концепция криптографической системы с открытым ключом сформулирована Диффи (131йе) и Хеллманом (Не!!шап) [74]. Криптографическая система КБА была предложена в 1977 году Ривестом (К[тезг), Шамиром (БЬаппг) и Адлеманом (АЙ1ешап) [259]. С тех пор в области криптографии были достигнуты большие успехи.
Углубилось понимание криптографической системы КБА, и в ее современных реализациях представленные здесь основные методы существенно улучшены. Кроме того, разработаны многие новые методы доказательства безопасности криптографических систем. Например, Голдвассер (Оо!сЬтаззег) и Микали (М[сай) [123] показали, что рандомизация может выступать в роли эффективного инструмента при разработке безопасных схем кодирования с открытым ключом. Гольдвассер, Микали и Ривест [124] представили схему цифровой подписи, для которой доказана трудность ее подделки.
В книге Менезеса (Мепегез) и др. [220] представлен обзор прикладной криптографии. Эвристический р-подход, предназначенный для разложения целых чисел на множители, был изобретен Поллардом (Ро11агд) [242]. Представленный в этой книге вариант является версией, предложенной Брентом (Вгепг) [48]. Время работы наилучшего из алгоритмов, предназначенных для разложения больших чисел, приближенно выражается экспоненциальной функцией от кубического корня из и, где и — длина подлежащего разложению числа. Общий теоретико-числовой алгоритм разложения по принципу решета, разработанный Бахлером (ВиЫег) и др.
[51] как обобщение идей, заложенных в теоретико-числовой алгоритм разложения по принципу решета Полларда [243] и Ленстры и др. [201] и усовершенствованный Копперсмитом (Соррегзщ11)з) [69], — по-видимому, наиболее эффективный среди подобных алгоритмов для обработки больших входных чисел. Несмотря на то, что строгий анализ этого алгоритма провести сложно, при разумных предположениях можно оценить время его работы как Ь(1/3 и)ьаоз+'(') где Ь (сг и) = еб""1 ('"'""1 Метод эллиптических кривых, предложенный Ленстрой (1.епзпа) [202], может оказаться эффективнее для некоторых входных данных, чем теоретико-числовой метод решета, поскольку, как и р-метод Полларда, он достаточно быстро позволяет найти небольшой простой множитель р.
Время его работы при поиске множителя р оценивается как Ь (1/2, р) ~+'(~1. ГЛАВА 32 Поиск подстрок В программах, предназначенных для редактирования текста, часто возникает задача поиска всех фрагментов текста, которые совпадают с заданным образцом. Обычно текст — это редактируемый документ, а образец — искомое слово, введенное пользователем.
Эффективные алгоритмы решения этой задачи могут повышать способность текстовых редакторов к реагированию. Кроме того, алгоритмы поиска подстрок используются, например, для поиска заданных образцов в молекулах ДНК. Приведем формальную постановку задачи поиска подарок (згппд-ша1сЫпд ргоЫеш).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
