Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 226
Текст из файла (страница 226)
Было высказано предположение о том, что вычисления ясс( можно выполнить пакетно, накапливая произведение нескольких величин х; в строке с последующим использованием этого произведения при вычислении ясс) вместо величины х,. Приведите подробное описание того, как можно было бы реализовать эту идею, почему она работает и какой размер пакета можно было бы выбрать для достижения максимального эффекта при обработке 13-битового числа и. Задачи 31.1. Бинарный алгоритм ноиска наибольшего общего делителя На большинстве компьютеров операции вычитания, проверки четности (нечетное или четное данное число) и деления пополам выполняются быстрее, чем вычисление остатка. В этой задаче исследуется бинарный алгоритм ноиска наибольшего общего делиазелл (Ъ(паху ясб а(яопЗЪзп), позволяющий избежать вычисления остатков, которые используются в алгоритме Евклида.
зь Докажите, что если и а, и Ь четны, то ясс((а, 6) = 2 ясс((а/2,6/2). б. Докажите, что если а нечетно, а 6 четно, то пес)(а,Ь) = ясс1(а, Ь/2). а Докажите, что если и а, и 6 нечетны, то ясс)(а, Ь) = ксс1((а — 6)/2,Ь). г, Разработайте эффективный бинарный алгоритм поиска ксб для целых чисел а и 6, где а > 6, время работы которого равно 0(1яа). Предполагается, что на каждое вычитание, проверку на четиость и деление пополам затрачивается единичное время. 1027 Тлаеа 21. Теоретико-чиелоеые алгоршпаы 31.2. Анализ битовых операций в алгоритме Евклида гь Рассмотрим обычный, "карандашом на бумаге", алгоритм деления а на Ь, в результате выполнения которого получаются частное д и остаток г.
Покажите, что в этом методе требуется выполнить 0((1 +!8 о) 18 Ь) битовых операций. б. Определим функцию 1л(а,Ь) = (1+!ба)(1+186). Покажите, что количество битовых операций, которые выполняются процедурой Епс12п при сведении задачи вычисления величины 8со(а,Ь) к вычислению величины 8сс)(Ь, а шос) 6), не превышает с(1л(а, Ь) — 1л(6, а шод 6)) для некоторой достаточно большой константы с > О. в. Покажите, что выполнение алгоритма Епсщп(а, 6) требует в общем случае 0(12(а, Ь)) битовых операций и 0()72) битовых операций, если оба входных значения являются 17-битовыми числами. 31.3. Три алгоритма вычисления чисел Фибоначчи В этой задаче выполняется сравнение производительности работы трех методов вычисления и-го числа Фибоначчи Е„ при заданном и.
Считаем, что стоимость сложения, вычитания или умножения двух чисел независимо от их размера равна 0(1). а Покажите, что время работы прямого рекурсивною метода вычисления числа Е„на основе рекурреитного соотношения (3.22) увеличивается экспоненциально с ростом п. (См., например, процедуру Р!в на с.
814.) б. Покажите, как с помощью технологии запоминания вычислить число Р„за время 0(п). в. Покажите, как вычислить число Г„за время 0(1я и), используя только сложения и умножения целых чисел. (Указаниег рассмотрите матрицу (01) и ее степени.) г. Предположим теперь, что для сложения двух ~З-битовых чисел требуется время 9(!3), а для их умножения — время й(~32). Чему равно время работы перечисленных выше алгоритмов с учетом такой стоимости выполнения элементарных арифметических операций? ЗЕ4. Квадратичные вычеты Пусть р — нечетное целое число.
Число а Е е'" является квадратичным выр четам (ццадгайс гез)дпе), если уравнение х = а (шой р) имеет решение относительно неизвестного х. а. Покажите, что существует ровно (р — 1)/2 квадратичных вычетов по модулю р. 1020 Часть РИ. Избранные темы б.
Если число р — простое, то определим снмяел Лежандра (Ьейепгйе зугпЬо1) (Я) для а Е а.' как равный 1, если а — квадратичный вычет по модулю р, и — 1 р р в противном случае. Докажите, что если а б Ур, то = а(Р )г (упос) р) . р/ Разработайте эффективный алгоритм, позволяющий определить, является ли заданное число а квадратичным вычетом по модулю р. Проанализируйте время работы этого алгоритма.
в. Докажите, что если р — простое число вида 4Ь+ 3, а а — квадратичный вычет в Е„', то величина а"+' шог[ р равна квадратному корню а по модулю р. Сколько времени требуется для поиска квадратного корня квадратичного вычета а по модулю р? д Разработайте эффективный рандомизированный алгоритм поиска неквадратичного вычета по модулю, равному произвольному простому числу р. Другими словами, нужно найти элемент Жр, который не является квадратичным вычетом.
Сюлько в среднем операций требуется выполнить этому алгоритму? Заключительные замечания В книге Нивена (Х(реп) и Цукермана (Епс1сеппап) [263) содержится прекрасное введение в элементарную теорию чисел. У Кнута (КппгЬ) [209) приведено подробное обсуждение алгоритмов, предназначенных для поиска наибольших общих делителей, а также других основных теоретико-числовых алгоритмов. Бач (ВасЬ) [29) и Ризель (К(ейе!) [293) представили более современный обзор вычислительных приложений теории чисел. В статье Диксона (Вйхоп) [90) содержится обзор методов разложения н проверки простоты чисел.
В трудах юнференцин под редакцией Померанца (Рошегапсе) [278) содержится несколько превосходных обзорных статей. Позже Бач (ВасЬ) и Шаллит (БЬайй) [30) представили прекрасный обзор основ вычислительной теории чисел. В книге Кнута [209]з обсуждается история возникновения алгоритма Евклида. Он встречается в трактате "Начала" греческого математика Евклида, опубликованном в 300 году до н.э., в седьмой книге — в теоремах 1 и 2. Описанный Евклидом алгоритм мог быть получен из алгоритма, предложенного Евдоксом около 375 года до н.э. Не исключено, что алгоритм Евклида является старейшим нетривиальным алгоритмом; соперничать с ним может только алгоритм умноже- Имется русский перевод: Д.
Кнут. Искусство программированы, т. 2 Пазучисленные авгоритим, У ' изб — М. И.Д, "Вильяма'*. 2000. Глана 3!. Теоретико-числовые алгоритмы !029 ния, известный еще древним египтянам. В статье Шаллита [310] описана история анализа алгоритма Евклида. Авторство частного случая китайской теоремы об остатках (теоремы 31.27) Кнут приписывает китайскому математику Сунь-Цзы, жившему приблизительно между 200 годом до н.э. и 200 годом н.э. (дата довольно неопределенная). Тот же частный случай сформулирован греческим математиком Никомахусом (!ч!!сЬошасЬпз) около 100 года н.э.
В 1247 году он был обобщен Чином Чиу-Шао (СЬЬ!и СЬш-Я1ао). Наконец в 1734 году Л. Эйлер (1.. Еп!ег) сформулировал и доказал китайскую теорему об остатках в общем виде. Представленный в этой книге рандомизированный алгоритм проверки простоты чисел взят из статей Миллера (М!11ег) [253] и Рабина (КаЬ!и) [287]; это самый быстрый (с точностью до постоянного множителя) из известных рандомизированных алгоритмов проверки простоты.
Доказательство теоремы 31.39 слегка адаптировано по сравнению с тем, что было предложено Бачем (ВасЬ) [28]. Доказательство более строгого результата для процедуры Мил.ек-КАвпч принадлежит Монье (Мошег) [256,257]. В течение многих лет проверка чисел на простоту была классическим примером задачи, в которой рандомизация представлялась совершенно необходимой для создания эффективного (с полиномиальным временем работы) алгоритма. Однако в 2002 году Агравал (Айгакна!), Каял (Кауа!) и Саксема (Бахеша) [4] поразили всех открытием детерминированного алгоритма с полиномиальным временем работы для проверки простоты.
До того самым быстрым детерминированным алгоритмом был алгоритм Кохена (СоЬеп) и Ленстры ().епзпа) [72], выполнявшийся для входного числа и за время (18 п)обк'Я'к"), что несколько превышает полиномиальное время. Тем не менее для практических целей рандомизированные алгоритмы остаются более эффективными и предпочтительными. Обстоятельное обсуждение задачи поиска больших "случайных" простых чисел содержится в статье Бьючимина (ВеацсЬеппп), Брассарда (Вгаззагг!), Крипо (Сгереац), Готье (Оопбег) и Померанца (Рогпегапсе) [35]. Концепция криптографической системы с открытым ключом сформулирована Диффи (13!%е) и Хеллманом (Нейшап) [86].
Криптографическая система КБА была предложена в ! 977 году Ривестом (К!мезг), Шамиром (БЬаппг) и Адлеманом (А<Пешки) [294]. С тех пор в области криптографии были достигнуты большие успехи. Углубилось понимание криптографической системы КБА, и в ее современных реализациях представленные здесь основные методы существенно улучшены.
Кроме того, разработаны многие новые методы доказательства безопасности криптографических систем. Например„Голдвассер (Оо!дкиаааег) и Микали (М!сай) [14!] показали, что рандомизация может выступать в роли эффективного инструмента при разработке безопасных схем кодирования с открытым ключом. Голдвассер, Микали и Ривест [142] представили схему цифровой подписи, для которой доказана трудность ее подделки, эквивалентная трудности разложения больших чисел на множители.
В книге Менезеса (Мепегез), ван Ооршота (кап ОогзсЬо!) и Ванстоуна (Чапа!опе) [252] представлен обзор прикладной криптографии. шзо Часть етт Избранные теыы Эвристический р-подход, предназначенный для разложения целых чисел на множители, был изобретен Поллардом (Ройагб) [275]. Представленный в этой книге вариант является версией, предложенной Брентом (Вгепг) [55]. Время работы наилучшего из алгоритмов, предназначенных для разложения больших чисел, приближенно выражается экспоненциальной функцией от кубического юрия длины подлежащего разложению числа и. Обобщенный теоретико-числовой алгоритм разложения по принципу решета, разработанный Бахлером [ВцЫег), Ленстрой (Ьепзна) и Померанцем (Рошегапсе) [56] как обобщение идей, заложенных в теоретико-числовой алгоритм разложения по принципу решета Полларда (Ройал)) [276] и Ленсгры (1.епзгга) и др. [231] и усовершенствованный Копперсмитом [Соррегзш1йй) [76] и другими, по-видимому, наиболее эффективен в общем случае для обработки больших входных чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
