Возведение в степень по модулю

Алгоритмизация / Возведение в степень по модулю

Во многих задачах, в частности, в криптосистеме часто приходится вычислять

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.

Однако можно воспользоваться свойством возведения в квадрат, реализующим идею:
Вычисление остатка от деления x в степени y на N
Таким образом, чтобы вычислить xy % N, нужно перемножить те степени x, которые соответствуют ненулевым позициям в двоичной записи y:

x25 = x16 · x8 · x0

Реализация

#include <iostream>
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

  • Возвести в степень по модулю довольно легко, даже при больших входных значениях. А вот вычисление дискретного логарифма , то есть нахождение показателя степени


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *