Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| АЛГОРИТМ B.11
Вычисление модульных инверсий Вход: Модуль N ; элемент a Выход: [a−1 mod N ] (если существует) (d, X, Y ) := eGCD(a, N ) // заметьте, что Xa + Y N = gcd(a, N ) if d ƒ= 1 return “a не обратимо по модулю N ” Более сложная задача – это возведение в степень по модулю N , то есть, вычисление [ab mod N ] для основания a∈ZN и степени целого числа b > 0. (Когда b = 0, задача простая. Если b < 0 и a∈ZN* , то ab = (a−1)−b mod N и задача сводится к случаю возведения в степень с положительной степенью с учетом того, что можно вычислить инверсии, как обсуждалось в предыдущем разделе). Обратите внимание, что основ- ной метод, используемый в случае сложения и умножения (т.е., вычисления целого числа ab и последующей редукции этого промежуточного результата по модулю N ) здесь не работает: целое число ab имеет длину ab = Θ(logab ) = Θ(b • «a»), и даже хранение промежуточного результата ab потребует времени в степени «b» = Θ(log b). Эту проблему можно решить за счет редукции по модулю N на всех промежуточ- ных этапах вычисления, а не только редукции по модулю N в конце. Это влияет на хранение промежуточных результатов, «небольших» по всему объему вычислений. Даже с этим важным начальным результатом разработка полиномиально-времен- ного алгоритма для модульного возведения в степень, по-прежнему является не- тривиальной задачей. Рассмотрим примитивный метод алгоритма B.12, который просто выполняет b умножений на a. Это по-прежнему действует в течение време- ни, которое является степенью «b». Этот примитивный алгоритм можно рассматри- вать как основанный на следующем рекуррентном соотношении: [ab mod N ] = [a • ab−1 mod N ] = [a • a • ab−2 mod N ] = • • • Любой алгоритм, основанный на этом соотношении, потребует времени Θ(b). Мы можем сделать |