Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
132
Часть II. Математические основы
большей константой (отображающей затраты на быстрое преобразование Фурье). При относительно небольших размерах операндов (которые часто используются в современной криптографии) быстрое преобразование Фурье может даже ухудшить исходную оценку сложности. По этой причине в книге при умножении и делении быстрое преобразование Фурье не применяется. Итак, в дальнейшем при оценке сложности умножения и деления мы будем использовать интуитивные рассуждения.
Оценим временную сложность алгоритмов 4.1 и 4.2, используя более точные побитовые оценки Ов()- По теореме 4.1 при а > Ь наибольший общий делитель gcd(a,b) можно вычислить за O(loga) единиц времени. Если оба входных числа ограничены величиной а, то операция деления по модулю имеет сложность OB((logo)2), а временная сложность алгоритмов 4.1 и 4.2 имеет порядок 0B((loga)3).
Напомним примечание 4.1: мы описали наиболее простые, но не самые эффективные варианты алгоритмов. Как видим, наше упрощение оказалось слишком грубым!
Более тщательная реализация алгоритмов Евклида должна учитывать следующие обстоятельства.
1. Временная сложность операции деления, выполняемой при вычислении чисел а = bq + г, имеет порядок 0B(log а х log b).
2. Частные q\, 52,..., qk в уравнениях (4.3.3) удовлетворяют условию
к к
log qi = log Y[ Qi ^ log a. (4.3.12)
4=1 1=1
Следовательно, более точная оценка временной сложности алгоритма вычисления наибольшего общего делителя имеет следующий вид:
к
Y2 ° в (logo х log ft) ^ Ов ((logo)2) .
i=l
Эффективные реализации алгоритмов Евклида приведены в главе 1 книги [79].
В остальной части нашей книги при оценке сложности вычисления наибольшего общего делителя с помощью обоих алгоритмов Евклида мы будем использовать наиболее широко известную оценку 0B((loga)2).
4.3.2.5 Модулярная арифметика
Одним из наиболее важных детерминированных полиномиальных алгоритмов^ которые мы рассмотрим, является возведение в степень по модулю. Эта операция часто используется в криптографии с открытым ключом. Для начала кратко изложим основы модулярной арифметики (читатели, уже знакомые с модулярной арифметикой, могут пропустить этот раздел).
Глава 4. Вычислительная сложность 133
у(А'- A)(modn) = О,
Определение 4.4 (Деление по модулю). При заданных целых числах х и п > 1 операция "x(modn)" возвращает остаток от деления числа х на число п, т.е. неотрицательное целое число г 6 [0, п — 1], удовлетворяющее условию
х = кп + г
для некоторого целого числа к.
Теорема 4.2 (Свойства деления по модулю). Пусть х,у,п ф 0 — целые числа cgcd(y, тг) = 1. Операция деления по модулю имеет следующие свойства:
1. (х + y)(modn) = [(rc(modn)) + (y(modn))](rnodn);
2. (—x)(modn) = (n — x)(raodn) = n — (rc(modn));
3. (a>y)(modn) = [(rc(modn)) x (y(modn))](modn);
4. Обозначим через у-1 (mod n) величину, обратную ку no модулю п (multiplicative inverse of у modulo n). Она является единственным числом из отрезка [1, п — 1], удовлетворяющим условию
(y-y-1)(modn) = 1.
Доказательство. Мы докажем только свойства 1 и 4. (Свойства 2 и 3 читатели могут доказать самостоятельно (упражнение 4.4).)
Запишем х = кп + г, у = in + s, где 0 ^ г, s ^ п — 1.
Для свойства 1 имеем следующее.
(ж + y)(modn) = [(кп + г) + (?п + s)](modn) = = [(к + ?)п + (г + s)](modn) = = (г + s)(mod п) = = [(:r(modn)) + (y(modn))](modn).
Для свойства 4, учитывая, что gcd(y,n) = 1, и применяя обобщенный алгоритм Евклида 4.2 к исходным данным у и п, получаем целые числа Л и р, удовлетворяющие условию
у\ + пр = 1. (4.3.13)
Без потери общности можно утверждать, что А < п, поскольку в противном случае можно просто заменить число А величиной A(modn), а число р — числом ук + ц при некотором к, не нарушая справедливости соотношения (4.3.13). По определению 4.4 уА modn = 1. Следовательно, у-1 = А < п является величиной, обратной к числу у по модулю п. Докажем единственность числа у-1 на отрезке [1, п — 1]. Предположим, что существует еще одна величина, обратная к числу у по модулю п. Обозначим ее через А' € [1,п — 1], А' ф А. Тогда
134
Часть II. Математические основы
т.е.
у(Х'-Х) = ап, (4.3.14)
где а — некоторое целое число. Известно, что у = ?п + 1 при некотором целом числе ?. Следовательно, уравнение (4.3.14) принимает вид
(?п + 1)(А' — Л) = an,
или
Х'-Х = Ъп,
где Ь — некоторое целое число. Это противоречит нашему предположению, что Л и Л' принадлежат отрезку [1, п — 1]. Значит, Л' ф X. ?
Как и при делении рациональных чисел, деление чисел по модулю п определяется как умножение на обратное число. Разумеется, для этого необходимо, чтобы обратное число существовало. Итак, для любого числа у, удовлетворяющего условию gcd(y,n) = 1 выражение xy~l(modn) можно переписать в виде x/y(modn).
Поскольку для вычисления величины у~1 применяется обобщенный алгоритм Евклида, его сложность имеет порядок 0?((logn)2). Следовательно, временная сложность деления по модулю имеет порядок 0^((logn)2).
Из теоремы 4.2 следует, что модулярная арифметика очень похожа на целочисленную. Легко показать, что операции сложения и умножения подчиняются следующим законам коммутативности и ассоциативности (символ "о" обозначает либо сложение, либо умножение).
