Алгоритмы - построение и анализ (1021735), страница 195
Текст из файла (страница 195)
в) Докажите, что для г < Й < 1 справедливы соотношения Я;ь (х) = = Щ (х) шод Рьь (х) и Яь, (х) = Я; (х) гпос1 Рь (х). г) Предложите алгоритм вычисления А(хо), А(х1),..., А (х„1) со временем работы О (и 15~ и). 30-6. БПФ с использованием модульной арифметики Согласно определению, при вычислении дискретного преобразования Фурье требуется использовать комплексные числа, что может привести к потере точности из-за ошибок округления. Для некоторых задач известно, что ответы содержат только целые значения, поэтому желательно использовать вариант БПФ, основанный на модульной арифметике, чтобы гарантировать, что ответ вычисляется точно.
Примером такой задачи является умножение двух полиномов с целыми коэффициентами. В упражнении 30.2-6 предлагался подход, в котором используются модули длиной й (и) битов для вычисления ДПФ по п точкам. В данной задаче предлагается иной подход, в котором используются модули более подходящей длины 0(1яи); для его понимания следует ознакомиться с материалами главы 31.
Предполагается, что и является степенью 2. а) Пусть требуется найти наименьшее значение lс, такое что р = йп+ + 1 является простым числом. Предложите простое эвристическое доказательство того, что й примерно равно 1я п. (Значение 1с может быль больше или меньше, но в среднем нам придется рассмотреть 0 (1я п) возможных значений й.) Как ожидаемая длина р соотносится с длиной п? Предположим, что д является генератором Ер, и пусть ю = д" шой р. Глава 30. Полиномы и быстрое преобразование Фурье 953 б) Докажите, что ДПФ и обратное ДПФ являются вполне определенными обратными операциями по модулю р, если в качестве в используется главное значение корня и-й степени из единицы. в) Докажите, что БПФ и обратное ему преобразование по модулю р могут выполняться за время О (п18п), если при этом операции со словами длиной О (18 и) выполняются за единичное время.
(Значения р и тс считаются заданными.) г) Вычислите ДПФ по модулю р = 17 для вектора (0,5,3,7,7,2,1,6). Учтите, что генератором Е;т является д = 3. Заключительные замечания Подробное рассмотрение быстрого преобразования Фурье содержится в книге Ван Лона (ЧапЬоап) [303].
В работах Пресса (Ргезз), Фланнери (Р1аппегу), Тукольски (Тецко1з1су) и Ветгерлинга (Чепегйпй) [248, 249] предлагается хорошее описание быстрого преобразования Фурье и его приложений. Прекрасное введение в обработку сигналов, область широкого применения БПФ, предлагается в работах Оппенгейма (ОррепЬепп) и Шафера (ЯсЬаГег) [232], а также Оппенгейма и Уиллски (М11з1су) [233].
В книге Оппенгейма и Шафера также описаны действия в случае, когда п не является целой степенью 2. Анализ Фурье не ограничивается одномерными данными. Он широко используется в обработке изображений для анализа данных в двух и более измерениях. Многомерные преобразования Фурье и их применение в обработке изображений обсуждаются в книгах Гонзалеса (Попка!ех) и Вудса (%оооз) [127] и Пратта (Ргап) [246], а в книгах Толимьери (То!пшеп), Эн (Ап) и Лу (Ьп) [300] и Ван Лона (Чап Ьоап) [303] обсуждаются математические аспекты многомерных быстрых преобразований Фурье. Изобретение БПФ в середине 1960-х часто связывают с работой Кули (Соо!е!) и Таки (Ти1сеу) [68].
На самом деле БПФ неоднократно изобреталось до этого, но важность его в полной мере не осознавалась до появления современных компьютеров. Хотя Пресс, Фланнери, Тукольски и Веттерлинг приписывают открытие данного метода Рунге (Кцпйе) и Кенигу (Кбшй) в 1924 году, Хейдеман (НеЫешап), Джонсон (1оЬпзоп) и Баррус (Вштиз) [141] в своей статье утверждают, что БПФ открыл еще Гаусс (Овика) в 1805 г. ГЛАВА 31 Теоретико-числовые алгоритмы Раньше теория чисел рассматривалась как элегантная, но почти бесполезная область чистой математики. В наши дни теоретико-числовые алгоритмы нашли широкое применение. В определенной степени это произошло благодаря изобретению криптографических схем, основанных на больших простых числах.
Применимость этих схем базируется на том, что имеется возможность легко находить большие простые числа, а их безопасность — на отсутствии простой возможности разложения на множители произведения больших простых чисел. В этой главе изложены некоторые вопросы теории чисел и связанные с ними алгоритмы, на которых основаны важные приложения. В разделе 31.1 представлено введение в такие основные концепции теории чисел, как делимость, равенство по модулю и однозначность разложения на множители. В разделе 31.2 исследуется один из самых старых алгоритмов: алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя двух целых чисел.
В разделе 31.3 представлен обзор концепций модульной арифметики. Далее, в разделе 31.4 изучается множество чисел, которые являются кратными заданного числа а по модулю и, и показано, как с помощью алгоритма Евклида найти все решения уравнения ах = 61шодп). В разделе 31.5 представлена китайская теорема об остатках. В разделе 31.6 рассматриваются степени заданного числа и по модулю и, а также представлен алгоритм повторного возведения в квадрат (гереагег1-зоцаг!пй а!йопг!пп) для эффективного вычисления величины а шой и для заданных а, б и и.
Эта операция является стержневой при эффективном тестировании простых чисел и для многих современных криптографических схем. Далее, в разделе 3!.7 описывается криптографическая система с открытым ключом КБА. В разделе 31.8 исследуется рандомизированный тест простоты Глава 31. Теоретико-числовые алгоритмы 955 чисел, с помощью которого можно организовать эффективный поиск больших простых чисел, что является важной задачей при создании ключей для криптографической системы КБА. Наконец, в разделе 31.9 представлен обзор простого, но эффективного эвристического подхода к задаче о разложении небольших целых чисел на множители.
Интересно, что задача факторизации — одна из тех, которой, возможно, лучше было бы оставаться трудноразрешимой, поскольку от того, до какой степени трудно раскладывать на множители большие целые числа, зависит надежность КБА-кодирования. Размер входных наборов данных и стоимость арифметических вычислений Поскольку нам предстоит работать с большими целыми числами, следует уточнить, чтб будет подразумеваться под размером входных данных и под стоимостью элементарных арифметических операций. В этой главе "большой ввод" обычно обозначает ввод, содержащий "большие целые числа", а не ввод, содержащий "большое количество целых чисел" (как зто было в задаче сортировки).
Таким образом, размер входных данных будет определяться количествам битов, необходимых для представления этих данных, а не просто количеством чисел в них. Время работы алгоритма, на вход которого подаются целые числа аз, аз,..., аы является волииомиальиым (ро1упоппа1), если он выполняется за время, которое выражается полиномиальной функцией от величин 1к (а1), 1к (аз),..., 1к (аь), те. если это время является полиномиальным по длине входных величин в бинарном представлении. В большей части настоящей книги было удобно считать элементарные арифметические операции (умножение, деление или вычисление остатка) примитивными, т.е.
такими, которые выполняются за единичный промежуток времени. При таком предположении в качестве основы для разумной оценки фактического времени работы алгоритма на компьютере может выступать количество перечисленных арифметических операций, выполняющихся в алгоритме. Однако если входные числа достаточно большие, то для выполнения элементарных операций может потребоваться значительное время, и удобнее измерять сложность теоретико-числового алгоритма через количество бгияовых опереди» (Ыг орегайоп). В этой модели для перемножения двух 13-битовых целых чисел обычным методом необходимо О (13з) битовых операций. Аналогично, операцию деления 13-битового целого числа на более короткое целое число или операцию вычисления остатка от деления Д-битового целого числа на более короткое целое число, с помощью простого алгоритма можно выполнить в течение времени О (,8з) (упражнение 31.1-11).
Известны и более быстрые методы. Например, время перемножения двух,9-битовых целых чисел методом разбиения равно 6 (131кз), а время работы самого производительного из известных методов равно 9 (~3 1к)3 1к 1я 13). Однако на практике Часть Ч11.
Избранные темы 956 зачастую наилучшим оказывается алгоритм со временем работы кз(132), и нвш анализ будет основываться именно на этой оценке. В этой главе алгоритмы обычно анализируются и в терминах количества арифметических операций, и в терминах количества битовых операций, требуемых для их выполнения. 31.1 Элементарные обозначения, принятые в теории чисел В этом разделе дается краткий обзор обозначений, которые используются в элементарной теории чисел, изучающей свойства множества целых чисел 2 = = (..., — 2, — 1, О, 1, 2,...) и множества натуральных' чисел Х = (О, 1, 2,...). Делимость и делители Основным в теории чисел является обозначение того факта, что одно целое число делится на другое. Обозначение с( ~ а (читается "Н двлива а", или ча делится на д") подразумевает, что для некоторого целого числа lс выполняется равенство а = Ы.
Число 0 делится на все целые числа. Если а > 0 и г( ) а, то Ц < )а). Если Ы ) а, то говорят также, что а — кратное (шп1бр!е) сь Если а не делится на ь(, то пишут и'1 а. Если ь( ( а и г( > О, то говорят, что с( — двливавиь (ОМзог) числа а. Заметим, что ь( ~ а тогда и только тогда, когда — г( ~ а, поэтому без потери общности делители можно определить как неотрицательные числа, подразумевая, что число, противоположное по знаку любому делителю числа а, также является делителем числа а. Делитель числа а, отличного от нуля, лежит в пределах от 1 до ~а~. Например, делителями числа 24 являются числа 1, 2, 3, 4, б, 8, 12 и 24.
Каждое целое число а делится на тривиальные делители (1Пуза1 б)у)зогз) 1 и а. Нетривиальные делители числа а также называются множителями (гасгогз) а. Например, множители числа 20 — 2, 4, 5 и 10. Простые и составные числа Целое число а > 1, единственными делителями которого являются тривиальные делители 1 и а, называют нросиаььм (ргппе) числом.
Простые числа обладают многими особыми свойствами и играют важную роль в теории чисел. Ниже приведено 20 первых простых чисел в порядке возрастания: 'Определение натуральных чисел в американской литературе отличается от определения натуральных чисел в отечественной математике, где Х = (1, 2,...). В данной главе мы будем использовать определение натуральных чисел из оригинального издания книги.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
