Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 49

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 311 >> Следующая

а о Ь mod п = Ь о a mod п (коммутативность),
а о (Ь о с) mod п = (а о Ь) о с mod п (ассоциативность).
В заключение заметим, что в определении операции деления по модулю х mod п (см. определение 4.4) величина к (частное от деления х на п) не важна. Следовательно, в тождестве
a;modn = ymodn, (4.3.15)
числа х и у могут отличаться на величину, кратную п. Следовательно, уравнение (4.3.15) можно переписать в виде
х = 2/(mod п)
или
2; (mod п) = у.
Эта операция называется сравнением по модулю п (congruence modulo п), а числа х и.у называются сравнимыми по модулю п.
Глава 4. Вычислительная сложность
135
4.3.2.6 Возведение в степень по модулю
При х,у < п определение числа х в степени у по модулю п (modular exponentiation) xy(modn) совпадает с определением обычной степени целого числа, т.е. произведению числа х самого на себя у раз, но только по модулю п.
ху =if хх.. .j(modn). у
Обозначим через у -г- 2 частное от деления числа у на 2 с округлением до целого числа.
\Ц, если у — четное число, у-=-2= < 2'
) ^2~, если у — нечетное число.
Применяя к умножению по модулю закон ассоциативности, получаем
у _ Г (ж2)у~2, если у — четное число, 1 (х2)у~2 х, если у — нечетное число.
Эта формула описывает популярный алгоритм возведения в степень по модулю, известный под названием "метода повторяющихся возведения в квадрат и умножения". Этот алгоритм сводится к следующему повторяющемуся процессу: разделить степень на 2, возвести в квадрат, и выполнить дополнительное умножение, если степень является нечетной. Рекурсивная версия этого алгоритма описана ниже.
Алгоритм 4.3. Возведение в степень по модулю ВВОД: х, у, п: целые числа, х > 0, у ^ 0, п > 1. ВЫВОД: 2^(modn)
mod_exp(s, у, п)
1. if у = 0 return(l);
2. if y(mod2) = 0 return(mod_exp (s2(modn),у ч- 2,n));
3. return^ - mod_exp (s2(modn),y ч- 2,n)(modn)).
Обратите внимание на третий шаг алгоритма 4.3, являющийся результатом рекурсивной реализации: выполнение операции "return" означает, что дальнейшие шаги алгоритма выполнить невозможно, поскольку операция "гег,шп(значение)" возвращает процесс вычислений в точку вызова функции mod_exp. Следовательно, если выполняется шаг 2, то шаг 3 не будет реализован.
136
Часть II. Математические основы
В качестве иллюстрации начнем алгоритм с вызова функции mod_exp(2,
Обратите внимание на то, что эти шесть строк содержат пять рекурсивных вызовов функции modjexp. Последняя строка "mod_exp(12,0,23)" означает "вер-1 нуть значение 1" и не является рекурсивным вызовом. Последнее значение, возвращаемое функцией mod_exp(2,21,23), равно 12 и может быть представлено, в следующем виде.
Оценим временную сложность функции mod_exp, реализующей алгоритм 4.3. Поскольку при у > 0 операция "поделить на два" выполняется за |k>g22/J + 1 единиц времени, прежде чем вычислит частное, равное нулю, вызов функции mod_exp(a:, у, п) порождает ровно [log2 у\ +1 рекурсивных вызовов, прежде чем достигнет завершения алгоритма. Каждый рекурсивный вызов содержит возведение в квадрат или возведение в квадрат с последующим умножением, порядок сложности которого равен Од ((log ж)2). Если предположить, что х и у меньше п, временная сложность алгоритма4.3 оценивается величиной порядка Ов((logп)3).
Как и вычисление наибольшего общего делителя, возведение в степень по модулю носит последовательный характер. Это кажется очевидным вследствие повторяющихся операций возведения в квадрат: х4 можно вычислить, толька вычислив значение х2. За все время существования этого алгоритма никому не удалось улучшить порядок сложности 0?((k>gn)3) (без применения быстрота преобразования Фурье).
Оценки сложности основных операций в модулярной арифметике приведены на рис. 4.3. Следует отметить, что операция деления по модулю не сводится] к обычному делению, поскольку 0 ^ а, Ь < п, а значит, — п < а±Ь < 2п Следовательно,
21,23).
mod_exp(2,21,23) =
= 2 - mod_exp(4(=22(mod 23)), 10,23) = 2 - mod_exp(16(EE42(mod 23)), 5,23) = 2 • 16 ¦ mod_exp(3(=l62(mod 23)), 2,23) = 2 • 16 • mod_exp(9(=32(mod23)), 1,23) = 2 • 16 • 9 - mod_exp(12(=92(mod23)),0,23) = 2-16-9-1
шаг 3) 'шаг 2) 'шаг 3) шаг 2) 'шаг 3) ]шаг 1)
12 = 2 • 16 • 9 = 2
422)2-(((22)2)2)Vod23).
a ± Ь,
a ± b(mod п) — < a ± Ь — п,
a ± Ь, если 0 ^ a ± Ъ < п,
a±b — n, если а ± Ь ^ п, n+(a±b), еслиа±Ь<0.
Глава 4. Вычислительная сложность
137
Операция над а.йеу [1,и) Сложность
а±Ъ (modп) ов (log п)
а - 6 (mod п) Од ((log п)2)
б-1 (modn) 0B((logn)2)
а/6 (mod п) Од ((log n)2)
ab (modn) Од ((log n)3)
Рис. 4.3. Поразрядные оценки сложности основных операций в модулярной арифметике
4.4 Вероятностное полиномиальное время
Общепризнанно, что если язык не принадлежит классу V, то не существует машины Тьюринга, которая распознавала бы его и всегда была эффективной2. Однако существует класс языков, обладающих следующим свойством: их принадлежность к классу V не доказана, но они всегда эффективно распознаются определенной машиной Тьюринга, которая иногда делает ошибки.
Причина, по которой машина Тьюринга может иногда делать ошибки, заключается в том, что некоторые такты являются случайными (random move). Иногда случайные такты приводят к правильным результатам, а иногда — нет. Такая модель называется недетерминированной машиной Тьюринга (non-deterministic Turing machine). Подкласс задач принятия решений, который мы рассмотрим, обладает свойством, ограничивающим вероятность ошибки.
Предыдущая << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed