Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
П+1 = - Tiqi+1. (4.3.7)
Заменяя числа rj_i и Ti в правой части уравнения (4.3.7) с помощью уравнения (4.3.5), получаем следующее:
П+\ = a(Ai_i - qi+iXi) + Ь(/м-1 - Qi+iHi)- (4.3.8)
Сравнивая уравнения (4.3.8) и (4.3.5), получаем для г = 0,1,..., к — 1 следующие соотношения.
Aj+l = Ai_i — %+iA, ^4 3 9^
Эти два уравнения лежат в основе общего метода, позволяющего накапливать промежуточные частные в ходе вычисления наибольшего общего делителя (алгоритм 4.2).
Примечание 4.1. Для упрощения описания алгоритмов 4.1 и 4.2 мы пожертвовали эффективностью. В следующих двух разделах (4.3.2.3 и 4.3.2.4) мы проанализируем их временную сложность и сравним полученные результаты с наилучшими оценками, достигнутыми при вычислении наибольшего общего делителя. о
4.3.2.3 Временная сложность алгоритмов Евклида
Оценим временную сложность обоих алгоритмов Евклида. Очевидно, что количество рекурсивных вызовов в алгоритме 4.1 равно количеству циклов в алгоритме 4.2, которое в свою очередь равно числу к — т.е. числу уравнений в последовательности (4.3.3).
130
Часть II. Математические основы
Алгоритм 4.2. Обобщенный алгоритм Евклида ВВОД: Целые числа а > Ь ^ 0.
ВЫВОД: Целые числа А и /х, удовлетворяющие условию аХ + Ъц = gcd(a, Ъ).
1. (*Инициализация*)
г <— 0; r_i <— а; го <— Ь; A_i <— 1; р-\ *-0; Xq *-0; fio *-U-
2. (* Пока выполняется условие аА» + bpi = п *) while (rj = aAj + Ь/щ ф 0) do.
а) (* Символ -г обозначает деление целых чисел *)
б) (* Суммирование частных *)
Aj+i ¦— Aj_i — q\; <— — q/м',
в) г +— г + 1.
3. return ((Ai_i,
Рассмотрим случай, когда а > Ъ и проанализируем уравнение (4.3.7) при г = = 0,1,... к — 1. Возможен один из двух вариантов:
N < |ri_i|, (4.3.10)
или
Iri+il < |ri_i|. (4.3.11)
Учитывая, что rj+i < г$, приходим к выводу, что условие (4.3.11) является следствием условия (4.3.10). Следовательно, условие (4.3.11) является инвариантным. Это означает, что максимальное значение к ограничено величиной 2|а|. Если операция модулярной арифметики является элементарной и на нее затрачивается единица времени, то временная сложность алгоритма 4.1 ограничена величиной 2|а|. Это выражение является линейной функцией, зависящей от аргумента а.
Теорема 4.1. Наибольший общий делитель gcd(a, Ь) можно вычислить с помощью не более чем 2тах(|а|, |6|) операций модулярной арифметики. Следовательно, алгоритмы 4.1 и 4.2 завершатся по меньшей мере через 2тах(|а|, |Ь|) итераций, и
Первую половину теоремы 4.1 впервые доказал Ж. Ламе (1795-1870) (G. Lame). Ее можно считать первой теоремой в теории вычислительной сложности.
Последовательность уравнений (4.3.3) свидетельствует о линейной природе алгоритма Евклида. За все время его существования еще никому не удалось существенно сократить количество операций, необходимых для вычисления наибольшего общего делителя.
Глава 4. Вычислительная сложность
131
4.3.2.4 Две оценки вычислительной сложности
При оценке вычислительной сложности алгоритма часто невозможно или не обязательно уточнять постоянный коэффициент, входящий в выражение, ограничивающее меру сложности. О-символика (order notation) облегчает задачу оценки сложности.
Ъпределение 4.2 (О-символика). Символом 0(/(п)) обозначается цЬункция jj{p), для которой существует константа с > 0 и натуральное число N, такие что \g(n)\ ^ с|/(п)| для всех n ^ N.
Используя О-символику, мы можем выразить временную сложность алгоритмов 4.1 и 4.2 как O(logo). Обратите внимание на то, что в этом выражении мы заменили величину |о| числом log а, не указывая явно основание логарифма (поскольку по умолчанию предполагается, что основание натурального логарифма е не указывается). Читатель может самостоятельно убедиться, что в оценке сложности можно использовать любое основание Ь > 1 (упражнение 4.10).
До сих пор мы предполагали, что выполнение одной операции модулярной арифметики выполняется за одну единицу времени, т.е. ее временная сложность имеет порядок 0(1). На самом деле операция "о mod b" в общем случае использует деление о -?- Ь, с помощью которой в алгоритме 4.2 вычисляются частные. Следовательно, временная сложность операции модульной арифметики должна зависеть от размеров двух операндов. С практической точки зрения (смысл которой описан в разделе 4.4.6) оценка сложности 0(1) для операции деления является слишком грубой.
Для оценки сложности поразрядных (bitwise) арифметических операций используется модифицированная О-символика. В поразрядных вычислениях все переменные принимают значения нуль или единица, а операции носят не арифметический, а логический характер: Л (для операции AND), V (для операции OR), © (для операции XOR, т.е. "исключающего или") и (для операции NOT).
Определение 4.3 (О-символика для поразрядных вычислений.). При оценке сложности поразрядных вычислений вместо символа 00 используется символ
ОвО-
В рамках модели поразрядных вычислений на сложение и вычитание двух целых чисел г и j затрачиваются max(|i|,побитовых операций, т.е. порядок временной сложности равен 0(тах(|г"|, \ j\)). Интуиция подсказывает, что на умножение и деление двух целых чисел г и j затрачиваются |г| - \j\ побитовых операций, т.е. порядок их временной сложности равен 0(logz х logj). Следует отметить, что при использовании метода быстрого преобразования Фурье (БПФ) порядок сложности умножения (и деления) можно снизить до Os(log(z + j) х loglog(z + + j))- Однако эта оценка является лишь асимптотической и связана с намного
