Итак, теперь умеем умножать числа, но в алгоритмах ГОСТ Р 34.10-94 требу­ется уметь вычислять произведение двух чисел по модулю простого числа. Для его реализации необходимо произвести вычисление остатка от деления 2n-значного числа на n-значное. Эта операция называется редукцией по модулю. Вы­полнять ее можно двумя способами. Первый состоит в том, что необходимо выполнить процедуру деления и взять остаток. Второй метод носит имя П. Монтгомери, который предложил модифицировать саму операцию редук­ции. Что из этого получилось, рассмотрим далее.

Деление.

Алгоритм деления «лесенкой», знакомый всем из начальной школы, помога­ет и здесь. Просто он достаточно точно формализован. Заодно он позволяет попутно получить остаток. Однако для его выполнения нам потребуется деление длинного n-значного числа на короткое. Эту операцию можно выполнять с помощью следующего алгоритма.

Алгоритм 1.8. Деление С = А/х длинного числа А длины n цифр на цифру х с вычислением остатка r = A mod x

1.       Т:=0;

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

3.       Т:=Т*b + Аi;

4.       Ci:= Т mod x;

5.       T:=Т/х;

6.       r:=Т;

7.       конец.

Теперь алгоритм «длинного» деления. Отметим, что он никак не обрабаты­вает ситуацию, когда делитель равен нулю. Просто «конец» и все. В нашем контексте ситуация «деление на ноль» может возникнуть только по ошибке ап­паратуры или при некорректном подборе параметров. Последнее обнаружива­ется при отладке, а сбой в любом случае приведет к неверному результату.

Алгоритм 1.9. Деление «лесенкой» Q - |_А/В_| длинного числа А длины t цифр на В длины n цифр с вычислением остатка R=A mod В

1.       R:=0;Q:=0;

2.       если В = 0, то конец;

3.       ели t<n, то R := А; конец;

4.       если n = 1, то Q := |A/B0|; R := A mod Bo; конец;

5.       d := |b/Bn-1|; // нормализующий множитель

6.       V := В*d;    // нормализация

7.       U:=A*d;

8.       для i = t-1 … n выполнить 9-16;

9.       если Ui = Vn-1,то Qi-n:= b-1;

10.     иначе Qi-n := (Ui*b + Ui-1)/Vt-1;

11.     пока  Qi-n * (Vn-1 * b + Vn-2) > Ui * b2+ Ui * b + Ui-2 выполнить 12;

12.     Qi-n:=Qi-n -1;

13.     U:=U-Qi-n *V*bi-n;

14.     если U < 0, то выполнить 15-16;

15.     U := U+V*bi-1

16.     Qi-1 := Qi-1 -1;

17.     R := U/d;              // денормализация

18.     конец.

Заметим, что умножение на степени числа b означает всего лишь сдвиг вто­рого сомножителя, а в силу нашего представления длинных чисел в памяти это означает смещение индекса в соответствующем массиве.Как видно, алгоритм достаточно сложен. И хотя время его работы есть ве­личина порядка n2, практически вычислять остаток таким образом неэффек­тивно. Его можно использовать там, где требуется выполнить несколько опера­ций, и выигрыш изложенного ниже метода Монтгомери практически отсут­ствует или не заметен. В частности, это применительно в операциях по модулю q в алгоритме вычисления подписи.