Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| *Умножение Монтгомери
Хотя деление целых чисел (и, следовательно, модульная редукция) могут быть выполнены в течение полиномиального времени, алгоритмы для целочисленного деления медленные, в сравнении, например, с алгоритмами для целочисленного умножения. Умножение Монтгомери дает способ выполнения модульного умно- жения без выполнения каких-либо затратных модульных редукций. Поскольку требуется предварительная и заключительная обработка, метод выгоден только тогда, когда несколько модульных умножений будет сделано последовательно, как, например, при вычислении модульного возведения в степень. Зафиксируем нечетный модуль N, по отношению к которому должны быть выполнены модульные операции. Пусть R > N будет степенью двух, скажем R = 2w , и заметьте, что gcd(R, N ) = 1. Ключевое свойство, которое мы будет использовать состоит в том, что деление на R – быстрое: коэффициент x при делении на R получается при простом сдвиге x вправо w позиций, и [x mod R] является только w битов с наименьшими значениями x. Определим представление Монтгомери x∈ ZN* с помощью x¯ [xR mod N ]. Умножение Монтгомери x¯, y¯ ∈ ZN* определяется как Mont(x¯, y¯) [x¯y¯R−1 mod N ]. (Ниже мы покажем, как это можно вычислить без каких-либо затратных мо- дульных редукций). Заметим, что Mont(x¯, y¯) = x¯y¯R−1 = (xR)(yR)R−1 = (xy)R = oxdy m N. Это означает, что можно умножить несколько значений в ZN посредством: (1) пре- образования в представление Монтгомери, (2) выполнением всех умножений с ис- пользованием умножения Монтгомери, чтобы получить конечный результат, а затем (3) преобразования результата из представления Монтгомери, назад к стандартному представлению. Пусть α [−N −1 mod R] – значение, которое может быть пред- варительно вычислено. (Вычисление α, преобразование в представление Монтго- мери/из него, также может быть выполнено без каких-либо затратных модульных редукций; подробности не входят в сферу наших интересов). Чтобы вычислить c Mont(x, y) без каких-либо затратных модульных редукций сделаем следующее: 1. Пусть z := x • y (по целым числам). 2. Зададим cr := (z + [zα mod R] • N ) /R. 3. Если cr < N, то зададим c := cr; иначе c := cr − N . Чтобы убедиться в работоспособности этого, сначала нужно проверить, что шаг 2 правильно определен, а именно, что числитель делится на R. Это следует из того, что z + [zα mod R]•N=z+zαN = z − zN −1N = 0 mod R. 329 Далее обратите внимание, что cr = z/R mod N после шага 2; кроме того, по- скольку z < N 2 < RN , мы имеем 0 < cr < (z + RN )/R < 2RN/R = 2N . Но тогда [cr mod N ] = cr если cr < N , и [cr mod N ] = cr − N if cr > N . Мы приходим к выводу, что c = [cr mod N ] = [z/R mod N ] = [xyR−1 mod N ], что и требовалось доказать. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|