Во многих задачах, в частности, в криптосистеме часто приходится вычислять
{\displaystyle{x^y\ \% \ N}}
для {\displaystyle{x}}, {\displaystyle{y}} и {\displaystyle{N}}, состоящих из нескольких сотен битов. Как это сделать быстро?
Результатом такого вычисления является остаток по модулю {\displaystyle{N}}, то есть число длиной несколько единиц — десятков битов.
Однако само {\displaystyle{x^y}} может иметь гораздо большую длину.
Если в двоичной записи {\displaystyle{x^y}} больше 32 битов, его уже невозможно представить в разрядной сетке типа int. Поэтому применение алгоритма, выполняющего сначала возведение в степень, а затем деления с вычислением остатка, сильно ограничено разрядной сеткой и требуемым объемом вычислений.
Значение {\displaystyle{x^y \ \% \ N}} можно вычислить, начав с 1 и {\displaystyle{y}} раз умножив на {\displaystyle{x}}(каждый раз по модулю {\displaystyle{N}}).
При этом все промежуточные результаты
- {\displaystyle{x \ \% \ N}}
- {\displaystyle{x^2 \ \% \ N}}
- {\displaystyle{x^3\ \% \ N}}
- …
- {\displaystyle{x^y\ \% \ N}}
не превосходят {\displaystyle{N}}, и каждое умножение будет сравнительно быстрым.
Возникает другая проблема: чем больше величина {\displaystyle{y}}, тем больше времени требуется на выполнение операций умножения. Причем время работы такого алгоритма будет расти пропорционально {\displaystyle{y}}.
Однако можно воспользоваться свойством возведения в квадрат, реализующим идею:
{\displaystyle x^y ={\begin{cases} x^{ {\left[ y/2 \right]}^2} && && если \ число \ четное\\ x \cdot x^{ {\left[ y/2 \right]}^2} && && если \ число \ нечетное\\\end{cases}}}
Операция [] обозначает взятие целочисленного частного.
Таким образом, чтобы вычислить {\displaystyle{x^y \ \% \ N}}, нужно перемножить те степени {\displaystyle{x}}, которые соответствуют ненулевым позициям в двоичной записи {\displaystyle{y}}:
{\displaystyle{x^{25} \ =\ x^{16} \ \cdot \ x^8 \ \cdot \ x^1}}
Реализация на C++
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
unsigned long int modexp(unsigned long int x, unsigned long int y, unsigned long int N)
{
if (y == 0) return 1;
unsigned long int z = modexp(x % N, y / 2, N) % N;
if (y % 2 == 0)
return (z * z) % N;
else
return ((x % N) * ((z * z) % N)) % N;
}
int main()
{
unsigned long 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;
}
Результат выполнения
