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

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

 

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

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 · x1

Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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 % 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

  • Елена, большое спасибо! Я переделал вашу функцию modexp для работы с числами типа __int64. В Visual Studio 2015 все компилируется и работает без ошибок. Желаю успехов!

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

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