Обозначения.

Теперь мы будем решать задачу вычисления значения С = AB(mod P), где Р — простое число длины n цифр, А и С — числа меньшие Р, В — число длины s цифр.

Бинарный алгоритм возведения в степень

Известный всем из школы алгоритм возведения в степень В путем В-1 ум­ножения очень неэффективен. При малых значениях В он еще приемлем, но при В порядка 2256 его сложность превышает всякие разумные пределы. Одна­ко можно воспользоваться алгоритмом, который называется бинарным алго­ритмом (иногда его называют схемой Горнера или дихотомическим алгорит­мом). Идея его построения состоит в следующем. Число В можно разложить по степеням 2 следующим образом:

ms-l

В= ∑2i * Bi, где Вi = 0 или 1.                                                                            (1.1)

i=0

Нетрудно видеть, что тогда

A = AB0 *( AB1 *(…*( ABms-1)2…)2)2 (1.2)

Алгоритм 1.11. Бинарный алгоритм возведения в степень C = AB(modP)

1.   С:=1;

2.   для i = ms-l…0 выполнить 3-4;

3.   C:=C2(mod P);

4.   если В.=1, то С := С Ч А (mod P);

5.   конец.

Теперь покажем, как можно использовать операцию Монтгомери для вычисления степени по модулю. При этом бинарный алгоритм возведения слегка видоизменяется. Идея такова: С = Ав (mod Р) = f-1(f(A)B) (mod P). Поскольку f-изоморфизм полей, то эта формула верна.

Алгоритм 1.12. Бинарный алгоритм возведения в степень С -Ав (mod Р) с использованием операции Монтгомери

1.   z := -Р0-1 (mod b);

2.   C:=f(1);

3.   D:=f(A);

4.   для i = ms-1…0 выполнить 3-4;

5.   С := CoC (mod P);

6.   если Вi=1, то С := CoD (mod P);

7.   C:=f-1(C);

8.   конец.

Здесь как будто замедлены вычисления, в виду наличия дополнительных операций вы­числения f(l), f(A), f-1(С). Однако при этом можно ускорить вы­числения произведений, количество которых больше, что в сумме дает выигрыш. В дальнейшем не будем приводить тексты программ, использующих операцию Монтгомери. Для простоты используются функции MulMod и SquareMod.

Обобщение бинарного алгоритма.

Пойдем дальше и запишем В в виде суммы степеней числа q = 2k для некоторого заранее выбранного параметра к:

ms/k — 1

B = ∑ qi * Bi , где Bi = 0…q-1                                                                              (1.3)

i=0

Подобно бинарному алгоритму это приводит к следующей формуле для вычисления степени:

A = AB0 *( AB1 *(…*( ABms/k-1)q…)q)q

Алгоритм возведения, использующий эту формулу, работает побыстрее бинарного алгоритма. Однако сначала для его использования необходимо под­готовить таблицу Tab степеней числа A: Tab[i]=Ai+1, i=0…q-2.

Алгоритм 1.13. k-арный алгоритм возведения в степень C = AB(mod P)

1.   Tab[0]:=A;

2.   для i = 1.. .q -2 выполнить шаг 3;

3.   Tab[i] := Tab[i-1] Ч A (mod P);

4.   C:=1;

5.   для i = -1.. .0 выполнить 6-7;

6.   С := Сq (mod P);

7.   если Вi ≠ 0,то С:=С Ч Таb[Вi-1](mod Р);

8.   конец.

Оценим трудоемкость реализации этого алгоритма вычисления степени. Очевидно он требует выполнения q-2 операций модулярного умножения при подготовке таблицы Tab, ms операций возведения в квадрат и в среднем (q-1)/q * ms/k умножений на элементы таблицы Tab. Если считать вычисление квадрата обычным умножением, получается средняя трудоемкость алгоритма q — 2 + ms + (q-1)/q * ms/k модулярных умножений. Ниже приведена таблица среднего количества умножений при возведении в степень с помощью к-арного алгоритма для ms = 256 (ситуация ГОСТ Р 34.10-94).

Одновременное вычисление произведения степеней

Приведенные выше алгоритмы возведения в степень с использованием за­ранее подготовленных таблиц вполне применимы при вычислении значения подписи и в первом возведении при проверке ЭЦП. Однако существует воз­можность вычислять произведение нескольких степеней параллельно. Вот как это делается. Пусть нам необходимо вычислить произведение С = ∏AjBj (mod P).

j=1

Воспользовавшись формулой (1.2), получим

∏AjBj = ∏AjBj0 *( ∏AjBj1*(…*( ∏ABjms-1)2…)2)2

j j j j

При этом Вij обозначает i-й двоичный разряд числа Вj. Если предварительно заготовить таблицу значений произведений вида ∏Ajuj для всех наборовj=1

{uj}(j=l…t), uj = 0 или 1, то дальнейшие вычисления будут состоять только в возведении во вторую степень и умножении на подходящие элементы табли­цы. Совсем как в бинарном алгоритме возведения в степень.