Длинные числа. Вычисление обратного по модулю

При проверке ЭЦП необходимо вычислить величину v = (h(M₁))^q-2 (mod q). Это можно сделать, по крайней мере, двумя способами:

возведением в степень и вычислением обратного с помощью расширенного алгоритма Евклида. Действительно, в теории чисел известна малая теорема Ферма, которая ут­верждает, что если р — простое число, а — целое число, не делящееся на р, то а^р-1 ≡ 1 (mod p).

Отсюда следует, что

а^р-2 ≡ a^-1 (mod p).

При этом а^-1 есть такое целое число, что aЧa^-1 ≡ 1(mod p). Это число называ­ется мультипликативным обратным а по модулю р.

С другой стороны, поскольку а и р взаимно простые, то существуют такие целые числа х и у, что ах+ру = 1. Если перейти к сравнениям mod p, то мы получим  ах ≡ 1 (mod p).

Откуда

х ≡ a^-1 (mod p)

и значит

х ≡ а^р-2 (mod p).

Для нахождения таких чисел х и у можно использовать так называемый расширенный алгоритм Евклида.

Алгоритм 1.19. Расширенный алгоритм Евклида, вычисления d = НОД(а,b) и х и у, что ax + by = d

1.       если b = 0, то d := а; х := 1; у := 0;

2.       х₂ := 1; х, := 0; у₂ := 0; у₁ := 1; а₁:=а; b₁:=b;

3.       пока b > 0 выполнить 4-5;

4.       q := |a₁/b₁|; r := а₁ — qb₁; х := х₂ – qx₁; у := у₂ – qy₁;

5.       a₁:= b,; b₁:= г; х₂ := x₁; x₁ := х; у₂ := y₁; y₁ := у;

6.       d:= a₁;x:=x₂;y :=у₂;

7.       конец.

Программную реализацию функции вычисления мультипликативного об­ратного с использованием расширенного алгоритма Евклида оставим в качестве упражнения. Скажем только, что с его помощью можно достичь довольно немалого ус­корения. Остался небольшой «грешок» при реализации операции Монтгомери. Была обещана функция, вычисляющая параметр z = -Р₀^-1 (mod b). Малая теоре­ма Ферма нам не подходит, поскольку модуль в данном случае не простой (на­помним, b = 2^m). Но можно воспользоваться ее обобщением, теоремой Эйлера:

если а и с — взаимно простые целые числа, то

аф^(с) = 1 (mod с).

(ф — функция Эйлера).

Таким образом, аф^(с)-1 = a^-1 (mod с).

В данном случае модулем является число b =2^m. Поэтому ф(b) = 2^m-1 и ф(b)-1 = 2^m-1-1 — число, двоичная запись которого состоит из m-1 единичного разря­да: 11…11₂. Воспользуемся би­нарным алгоритмом для вычисления значения a^-1 mod b. Заметим при этом, что a^-1 mod b существует только при а взаимно простом с числом и, т.е. при нечет­ном а.

Алгоритм 1.20. Алгоритм вычисления z = -a^-1 (mod 2^m)

1.       если а четно, то z=0; конец;

2.       d := a;

3.       повторить m-2 раза шаги 4-5;

4.       d := d² (mod 2^m):

5.       d := d Ч a (mod 2^m);

6.    конец.

Здесь предполагаем, что m — длина машинного слова и приве­дение к модулю 2^m выполняется при умножении автоматически. Если это не так, необходимо выполнить эту редукцию перед возвратом результата.