Во многих задачах, в частности, в криптосистеме часто приходится вычислять
xy % N
для x, y и N, состоящих из нескольких сотен битов. Как это сделать быстро?Результатом такого вычисления является остаток по модулю N, то есть число длиной несколько единиц — десятков битов.
Однако само xy может иметь гораздо большую длину.
Если в двоичной записи xy больше 32 битов, его уже невозможно представить в разрядной сетке типа int.
Поэтому применение алгоритма, выполняющего сначала возведение в степень, а затем деления с вычислением остатка, сильно ограничено разрядной сеткой и требуемым объемом вычислений.
Значение xy % N можно вычислить, начав с 1 и y раз умножив на x (каждый раз по модулю N). При этом все промежуточные результаты
x % N → x2 % N → x3 % N → … → xy % N
не превосходят N, и каждое умножение будет сравнительно быстрым.
Возникает другая проблема: чем больше величина y, тем больше времени требуется на выполнение операций умножения. Причем время работы такого алгоритма будет расти пропорционально y.
Однако можно воспользоваться свойством возведения в квадрат, реализующим идею:
Таким образом, чтобы вычислить xy % N, нужно перемножить те степени x, которые соответствуют ненулевым позициям в двоичной записи y:
x25 = x16 · x8 · x1
Реализация на C++
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int modexp(int x, int y, int N)
{
if (y == 0) return 1;
int z = modexp(x, y / 2, N);
if (y % 2 == 0)
return (z*z) % N;
else
return ((x % N) *((z*z) % N)) % N;
}
int main()
{
int x, y, N;
cout << "x= "; cin >> x;
cout << "y= "; cin >> y;
cout << "N= "; cin >> N;
cout << modexp(x, y, N);
cin.get(); cin.get();
return 0;
}
Результат выполнения
Назад: Алгоритмизация
Комментариев к записи: 1