Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 208
Текст из файла (страница 208)
Квадратичные вычеты Пусть р — нечетное целое число. Число а Е Е' является квадратичр ным вычеииии (Чпадгайс гезЫпе), если уравнение хз = а(тасар) имеет решение относительно неизвестного х. а) Покажите, что существует ровно (р — 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]. Время работы наилучшего из алгоритмов, предназначенных для разложения больших чисел, приближенно выражается экспоненциальной функцией от кубического корня из и, где и — длина подлежащего разложению числа.
Общий теоретико-числовой алгоритм разложения по принципу решета, разработанный Бахлером (ВиЫег) и др. [5 !] как обобщение идей, заложенных в теоретико-числовой алгоритм разложения по принципу решета Полларда [243] и Ленстры и др. [20!] и усовершенствованный Копперсмитом (Соррегзщ11!з) [69], — по-видимому, наиболее эффективный среди подобных алгоритмов для обработки больших входных чисел. Несмотря на то, что строгий анализ этого алгоритма провести сложно, при разумных предположениях можно оценить время его работы как Ь(1/3 и)ьаоз+'(') где Ь (сг и) = еб""1 ('"'""1 Метод эллиптических кривых, предложенный Ленстрой (1.епзпа) [202], может оказаться эффективнее для некоторых входных данных, чем теоретико-числовой метод решета, поскольку, как и р-метод Полларда, он достаточно быстро позволяет найти небольшой простой множитель р. Время его работы при поиске множителя р оценивается как Ь (1/2, р) ~+'(~1.
ГЛАВА 32 Поиск подстрок В программах, предназначенных для редактирования текста, часто возникает задача поиска всех фрагментов текста, которые совпадают с заданным образцом. Обычно текст — это редактируемый документ, а образец — искомое слово, введенное пользователем. Эффективные алгоритмы решения этой задачи могут повышать способность текстовых редакторов к реагированию. Кроме того, алгоритмы поиска подстрок используются, например, для поиска заданных образцов в молекулах ДНК. Приведем формальную постановку задачи поиска подарок (згппд-ша1сЫпд ргоЫеш). Предполагается, что текст задан в виде массива Т [1 ..и] длины и, а образец — в виде массива Р [1..гп] длины т < и. Далее, предполагается, что элементы массивов Р и Т вЂ” символы из конечного алфавита Е. Например, алфавит может иметь вид Е = 10, Ц или Е = (а, Ь,..., з). Символы массивов Р и Т часто называют сшроками (з1йпяз) или символами.
Говорят, что образец Р встречается в тексте Т со сдвигом а (оссигз чл1Ь зЫй а), если О < э < и — гп и Т [з+ 1..а+ гп] = Р [1..т] (другими словами, если при 1 < 1' < т Т [а+ 1] = Р [2]). (Можно также сказать, что образец Р встречается в тексте Т, начиная с позиции а + 1.) Если образец Р встречается в тексте Т со сдвигом а, то величину з называют допустимым сдвигам (ча!Ы зЫй); в противном случае ее называют педопустимьим сдвигам (1пча1Ы зЫй).
Задача поиска подстрок — это задача поиска всех допустимых сдвигов, с которыми заданный образец Р встречается в тексте Т. Эти определения проиллюстрированы на рис. 32.1. В представленном на этом рисунке примере предлагается найти все вхождения образца Р = аЬаа в текст Т = аЬсаЬааЬсаЬас. Образец встречается в тексте только один раз, со сдвигом а = 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
