Возведение в степень в длинной арифметике

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

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

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

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

_ms-l

В= ∑2ⁱ * B_i, где В_i = 0 или 1.                                                                            (1.1)

ⁱ⁼⁰

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

A = A^B0 *( A^B1 *(…*( A^Bms-1)²…)²)² (1.2)

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

1.   С:=1;

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

3.   C:=C²(mod P);

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

5.   конец.

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

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

1.   z := -Р₀^-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 = 2^k для некоторого заранее выбранного параметра к:

_{ms/k — 1}

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

ⁱ⁼⁰

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

A = A^B0 *( A^B1 *(…*( A^Bms/k-1)^q…)^q)^q

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

Алгоритм 1.13. k-арный алгоритм возведения в степень C = A^B(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).

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

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

^j=1

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

∏A_j^Bj = ∏A_j^Bj0 *( ∏A_j^Bj1*(…*( ∏A^Bjms-1)²…)²)²

^{j j j j}

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

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