Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
4.3.2 Алгоритмы и оценки вычислительной сложности
Рассмотрим три весьма полезных алгоритма с полиномиальным временем выполнения. По ходу изложения мы ознакомимся с языком программирования, который будем использовать в книге для описания алгоритмов и протоколов, примем некоторые обозначения, касающиеся оценки сложности алгоритмов и протоколов, и оценим временную сложность большого количества арифметических операций, которые наиболее часто применяются в криптографии.
Глава 4. Вычислительная сложность
127
Как упоминалось выше, машина Тьюринга представляет собой общую модель вычислений и позволяет формализовать понятие вычислительной сложности процедур. Однако, как правило, алгоритмы не описываются ни в терминах операции такой примитивной машины, ни в терминах микрокоманд современного компьютера (см. раздел 4.3.1). Для точного описания алгоритмов и математических выражений мы будем использовать псевдокод, который очень похож на большинство популярных языков программирования высокого уровня, таких как Pascal или С, и понятен всем читателям.
4.3.2.1 Наибольший общий делитель
Первый алгоритм, который мы изучим, — знаменитый алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя (алгоритм 4.1). Обозначим через gcd(a, b) наибольший общий делитель целых чисел а и Ь, т.е. наибольшее целое число, на которое делятся оба эти числа.
Алгоритм 4.1. Алгоритм Евклида для вычисления наибольшего общего делителя ВВОД: Целые числа а > b ^ 0. ВЫВОД: gcd(a, Ъ).
1. if b = 0 return (a).
2. return(gcd(b,amodft)).
В алгоритме 4.1 выражение "a mod b" обозначает остаток от деления числа а на число Ь. (В разделе 4.3.2.5 мы дадим формальное определение операции деления по модулю и приведем некоторые полезные сведения по модулярной арифметике.) Условие а > b ^ 0 приведено исключительно для простоты изложения. В конкретной реализации, если \а\ < \Ь\, можно заменить числа а и Ь их абсолютными величинами и вызвать функцию gcd(|b|, |a|).
Перейдем к анализу алгоритма 4.1. Для положительных чисел а ^ b всегда существует целое число q ф 0 (частное от деления числа а на число Ь) и число 0 ^ г < Ъ (остаток от деления числа а на число Ь), так что
a = bq + T. (4.3.2)
По определению на число gcd(a, b) делятся и число а, и число Ь. Из формулы (4.3.2) следует, что число г также должно делиться на gcd(a, b). Следовательно, число gcd(a, Ъ) равно gcd(6, г). Поскольку число т (остаток от деления числа а на число Ь) обозначается как a mod b, получаем, что
gcd(a, b) = gcd(b, a mod b).
Именно этот факт используется в алгоритме 4.1, в котором число gcd(a, b) рекурсивно определяется через число gcd(b, a mod b). Последовательность рекурсивных
128
Часть II. Математические основы
вызовов функции gcd приводит к решению следующего ряда уравнений, каждое из которых имеет вид (4.3.2) и образовано путем деления двух входных чисел:
a = bgi-r-ri, ri = г2<й + ^з,
(4-3.3)
Гк-з = rk-2Qk-i + rk-i, Гк-2 = Гк-iQk + Гк,
где Гк = О (условие окончания алгоритма), а д\, д2, ..., r\, г2,..., rk-i — нену-1 левые целые числа. Условие г* = 0 в последнем уравнении означает, что числе rfc_i является делителем чисел г^-2, rjt-з,.. -, т\ ив конце концов — чисел а и Ь.\ Ни один из других остатков в других уравнениях не обладает этим свойством (потому они и называются остатками, а не делителями). Итак, единственным де^ лителем является число r^-i- Следовательно, число г^-\ является наибольшие общим делителем чисел а и Ь, т.е. r^-i = gcd(a, Ь).
Например, вызов функции gcd(108,42) приведет к следующим рекурсивным^ вызовам:
gcd(108,42) = gcd(42,24) = gcd(24,18) = gcd(18,6) = gcd(6,0) = 6.
4.3.2.2 Обобщенный алгоритм Евклида
Алгоритм 4.1 не сохраняет промежуточные частные. Если бы он накапливал их в ходе вычислений наибольшего общего делителя, мы смогли бы вычислите кое-что еще. Попробуем определить, что же именно мы могли бы вычислить. |
Первое уравнение в последовательности (4.3.3) можно переписать в виде i
о + b(-qi) = ri-Умножая обе части уравнения на д2, получаем
am -f b[-qiq2) = nq2. Используя это уравнение и второе уравнение из последовательности (4.3.3), имеем
a(-Q2) + *>(1 + Qift) = Т2- (4.3.4)
Продолжая аналогичные вычисления для г = 1,2,... к, приходим к уравнению
(4.3.5)]
Глава 4. Вычислительная сложность
129
где числа Л,- и щ являются целыми и зависят от промежуточных остатков. Как мы убедились в разделе 4.3.2.1, продолжая вычисления, мы достигнем ситуации, когда Тк = 0. Следовательно,
аХк-1 + Ьцк-л = тк-1 = gcd(a, b). (4.3.6)
Алгоритм, на вход которого поступают числа а и Ь, а на выходе вычисляются числа Xk-i и Рк-1, удовлетворяющие условию (4.3.6), называется обобщенным алгоритмом Евклида (extended Euclid algorithm). Он будет широко использоваться в остальной части книги для деления целых чисел по модулю. А теперь уточним этот алгоритм, т.е. опишем общий метод накопления промежуточных частных.
Обратите внимание на уравнения (4.3.3) и на тот факт, что r_i = а,гп = = Ь, Л_1 = 1, = 0, Ло = 0, i-iQ = 1. Для г = 1,2,..., к — 1 из г-го уравнения в последовательности (4.3.3) следует, что
