Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Основные операции
- Вычисление модульных инверсий
| Модульная арифметика
Теперь обратим наше внимание на основные арифметические операции по модулю N > 1. Будем использовать ZN, чтобы ссылаться на множество{0, . . . , N − 1}, а также на группу, к которой приводит рассмотрение сложения по модулю N среди элементов этого множества. Основные операции Эффективные алгоритмы для основных арифметических операций над целы- ми числами, прямо подразумевают эффективные алгоритмы для соответствую- щих операций по модулю N . Например, вычисление модульной редукции [a mod N ] может быть выполнено в течение полиномиального времени в «a» и «N « при вычислении с остатком по целым числам. Далее рассмотрим модульные опера- ции на двух элементах a, b ∈ ZN, где «N « = n. (Заметим, что a, b имеют длину не более n. На самом деле, удобно предположить, что все элементы ZN имеют длину точно n, заполняя, при необходимости, левую часть нулями). Сложение a и b по модулю N может быть сделано при первом вычислении a + b, целого числа не более n + 1, а затем редукцией этого промежуточного результата по модулю N . Аналогично, умножение по модулю N может быть выполнено при первом вычис- лении целого числа по модулю ab длиной не более 2n и затем редукцией резуль- тата по модулю N . Поскольку все операции сложения, умножения и деления с остатком могут быть выполнены в течение полиномиального времени, они дают полиномиально-временные алгоритмы для сложения и умножения по модулю N . Вычисление модульных инверсий Наше обсуждение к настоящему моменту показало, как сложить, вычесть и ум- ножить по модулю N . Одна операция, которую мы пропустили, – это «деление» или, что то же самое, мультипликативные инверсии по модулю N . Напомним из раздела 8.1.2, что мультипликативная инверсия (по модулю N ) элемента a∈ZN – это элемент a−1∈ZN, такой что, a • a−1 = 1 mod N . Предположение 8.7 показы- 325 вает, что a имеет инверсию, если и только если gcd(a, N ) = 1, т.е., если и только если a ∈ ZN* . Таким образом, используя алгоритм Эвклида можно легко опре- делить, имеет ли данный элемент a мультипликативную инверсию по модулю N . С учетом N и a∈ZN при gcd(a, N ) = 1, предположение 8.2 говорит нам, что суще- ствуют целые числа X, Y при Xa + Y N = 1. Это означает, что [X mod N ] является мультипликативной инверсией a. Целые числа X и Y, удовлетворяющие Xa + Y N = 1, могут быть эффективно обнаружены с использованием расширенного алгоритма Эвклида eGCD, показанного в разделе B.1.2. Это приводит к следующему поли- номиально-временному алгоритму для вычисления мультипликативных инверсий: жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|