Во многих задачах, в частности, в криптосистеме часто приходится вычислять
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*z*z) % 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) Вначале небольшое дополнение. Если воспользоваться формулой (a·b) mod m = ((a mod m)·(b mod m)) mod m то при вычислении x^y % N каждый последующий элемент цепочки
x % N → x^2 % N → x^3 % N → … → x^y % N
начиная со второго, находится как произведение (по модулю N) предыдущего и первого элемента x^1 % N = x % N. Умножать на первый элемент порой удобнее, чем на x.
2) В заключительной части, где предлагается подход с возведением в квадрат, объяснения практически нет. Там не делается акцента на главном - уменьшении количества итераций наполовину для четного у и наполовину +1 для нечетного у.
В данном подходе базовым является случай с четным y = 2*k, когда цепочка вычислений имеет вид:
(x^1)^2 % N → (x^2)^2 % N → (x^3)^2 % N → … → (x^k)^2 % N
Каждый ее последующий элемент это результат умножения (по модулю N) предыдущего на x^2 или, с учетом п.1, это результат умножения (по модулю N) предыдущего на первый элемент (x^1)^2 % N
В случае с нечетным y (y = 2*k + 1) в конец цепочки добавляется еще одна итерация. Этот элемент - результат умножения (по модулю N) k-го элемента ((x^k)^2 % N) на число х, и имеет вид x*(x^k)^2 % N
3) Последний фрагмент лишен всякого смысла:
"Таким образом, чтобы вычислить x^y%N, нужно перемножить те степени x, которые соответствуют ненулевым позициям в двоичной записи y: x^25 = x^16 · x^8 · x^0"
Во-первых, выражение x^25 = x^16 · x^8 · x^0 неверно.
Во-вторых, оборот "Таким образом" подразумевает, что идущие за ним выкладки вытекают из вышеприведенного, но это совсем не так. Автор затрагивает тему разложения показателя степени по степеням двойки, но никак ее не раскрывает. (Мне кажется, что он сам ее не понимает).
Итак, одним из способов вычисления степени по модулю, а именно x^y mod N, является замена возведения в степень произведением. Для этого показатель степени у представляется в виде суммы степеней двойки, которые соответствуют ненулевым позициям в двоичной записи y. Продолжим на конкретном примере.
Пусть у = 25, что в двоичной записи соответствует 11001. Ненулевые значения находятся в 0-й, 3-й и 4-й позициях. Значит, у = 25 = 2^0 + 2^3 + 2^4 = 1 + 8 + 16.
Отсюда x^y = x^(1 + 8 + 16) = x * x^8 * x^16.
Поэтому x^y mod N = (x * x^8 * x^16) mod N = ((x mod N) * (x^8 mod N) * (x^16 mod N)) mod N
Дальнейшие вычисления не составляют никакой трудности
"Пусть у = 25... Отсюда x^y = x^(1 + 8 + 16) = x * x^8 * x^16."
Комментарий сам себе противоречит. Очень трудно понять, с чем Вы не согласны.