В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа это наименьшее число, которое делится и на a и на b . Например, НОК (6 , 8) = 24 . НОД и НОК тесно связаны между собой следующим соотношением: НОК ( a, b ) = ab НОД ( a, b ) . Данное утверждение приводится просто как констатация факта, доказывать его мы не будем. 11.3.5 Расширенный алгоритм Евклида Несмотря на всю свою прелесть, приведенный выше алгоритм не помог нам вычислить частное по модулю p . Для выполнения этой операции восполь- зуемся другим алгоритмом, известным как расширенный алгоритм Евклида. Его идея такова: вычисляя НОД ( a, b ) , мы можем найти два числа u и v , та- кие, что НОД ( a, b ) = ua + vb . Это позволит подсчитать значение выражения a/b (mod p ) . функция ExtendedGCD вход: a Положительное число. b Положительное число. выход: k Наибольший общий делитель a и b . ( u, v ) Целые числа такие, что ua + vb = k . assert a ≥ 0 ∧ b ≥ 0 ( c, d ) ← ( a, b ) ( u c , v c , u d , v d ) ← (1 , 0 , 0 , 1) while c 6 = 0 do Инвариант: u c a + v c b = c ∧ u d a + v d b = d q ← b d/c c ( c, d ) ← ( d − qc, c ) ( u c , v c , u d , v d ) ← ( u d − qu c , v d − qv c , u c , v c ) od return d , ( u d , v d ) Данный алгоритм во многом аналогичен алгоритму поиска НОД. Мы за- менили переменные a и b новыми переменными c и d , чтобы сохранить исход- ные значения a и b , так как они нужны для инварианта. Мысленно заменив c и d переменными a и b , мы получим в точности алгоритм поиска НОД. (Мы записали формулу d mod c в несколько ином виде, однако результат остается тем же.) Помимо этого, мы добавили четыре переменные, в которых хранятся значения коэффициентов инварианта; для каждого сгенерированного значе- ния c или d мы отслеживаем, как представить это значение в виде линейной комбинации a и b . Инициализировать значения этих переменных легко, пото- му что в начале алгоритма значению c присваивается значение a , а значению 11.3. Арифметика по модулю простого числа 219 d — значение b . Когда мы изменяем значения c и d в ходе цикла, обновить значения переменных u и v также несложно. Зачем нам нужен расширенный алгоритм Евклида? Пусть необходимо вычислить 1 /b mod p , где 1 ≤ b < p . Мы используем расширенный алго- ритм Евклида, чтобы определить ExtendedGCD ( b , p ). Мы знаем, что НОД b и p равен единице, поскольку p — простое число и других делителей кро- ме единицы и самого себя у него нет. Но в результате применения функции ExtendedGCD мы получаем числа u и v , такие, что ub + vp = НОД ( b, p ) = 1 . Другими словами, ub = 1 − vp или, что то же самое, ub = 1(mod p ) . Это зна- чит, что u = 1 /b (mod p ) , т.е. u является числом, обратным b по модулю p . Теперь частное a/b может быть подсчитано путем умножения a на u . Мы по- лучили формулу a/b = au (mod p ) , а подсчитать значение такого выражения не составляет труда. Расширенный алгоритм Евклида позволяет находить обратное число по модулю p , что, в свою очередь, может применяться для поиска частного по модулю p . Теперь вместе со сложением, вычитанием и умножением по модулю p мы можем выполнять все четыре элементарных операции над конечным полем по модулю p . Обратите внимание: значение u может быть отрицательным, поэтому, прежде чем использовать его в качестве обратного числа b , рекомендуется подсчитать u mod p . Внимательно посмотрев на алгоритм ExtendedGCD , вы заметите сле- дующее: если в качестве выходных данных нас интересует только значение u , можно не вычислять значения переменных v c и v d , поскольку они никак не влияют на вычисление u . Это позволяет немного сократить объем работы, необходимый для подсчета частного по модулю p . 11.3.6 Вычисления по модулю 2 Особым случаем арифметики по модулю простого числа является ариф- метика по модулю 2. Действительно, поскольку 2 — это простое число, мы можем выполнять любые операции по модулю 2. Вычисления по модулю 2 знакомы всем, кто когда-нибудь занимался программированием. На рис. 11.1 представлены таблицы сложения и умножения по модулю 2. Сложение по мо- дулю 2 — это не что иное, как операция “исключающее ИЛИ” (XOR), которая встречается во всех языках программирования. Умножение по модулю 2 — это всего лишь операция AND. В поле по модулю 2 существует только одна пара взаимно обратных чисел ( 1 / 1 = 1) , поэтому деление совпадает с умно- жением. Думаем, вас нисколько не удивит, что поле Z 2 является важным средством анализа многих алгоритмов, используемых компьютерами. |