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

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

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

{\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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
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;
}

Результат выполнения

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

1 комментарий к “Возведение в степень по модулю”

  1. Никита

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

Оставьте комментарий

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

Прокрутить вверх