Skip to content

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

Здравствуйте, сегодня поговорим об алгоритме быстрого возведения в степень по модулю, а также реализуем этот алгоритм на C++ под Visual Studio.

Общая информация

Этот алгоритм часто применяют в такой области, как «Защита информации» (косвенно, конечно). С его помощью могут реализовываться некоторые алгоритмы шифрования с открытым ключом, такие как «Шифр Эль-Гамаля», «Алгоритм Диффи-Хэллмана» и другие. Особенность алгоритма быстрого возведения в степень заключается в том, что он позволяет сократить время и количество вычислений для определенных задач, и, соответственно, увеличить скорость.

Постановка задачи

Алгоритм позволяет выполнить следующую задачу:
Необходимо вычислить ax modp, причем a, x, p могут быть большими.
modp — остаток от деления на число p.
К примеру, требуется вычислить 52 mod4 . Такую задачу почти каждый сможет решить в уме:
25 делим на 4, получаем остаток 1, то есть 52 mod4 = 1.

А что если увеличить числа, например, 5100 mod7, калькулятором не получится воспользоваться, так как не удастся вычислить 5100. Поэтому, можно воспользоваться алгоритмом быстрого возведения в степень.

Суть алгоритма

Чтобы вам было лучше понятно, суть алгоритма мы покажем на 2 примерах, надеюсь, после которых все будет понятно:

1 пример: 5100 mod7
Напомню общий вид выражения: ax modp

Пойдем по шагам:

Шаг 1
Перевести степень числа из десятичной в двоичную систему исчисления.
10010 = 11001002

Шаг 2
Определить число элементов n, которое равно количеству всех цифр степени в двоичной системе.
У нас число 11001002 , n = 7 (всего цифр).

Дополнение к шагу 2
В общем виде, число n = [log2x] + 1 , [] скобки означают, что нужно взять целую часть от числа.
Для нашего примера n = [log2100] + 1 = 6 + 1 = 7.

Шаг 3
Составить одномерный массив massive из n элементов, где :
massive[0] = a //первый элемент массива
massive[1] = massive[0]2modp // второй
massive[2] = massive[1]2modp // третий
…………………………………………………….и т.д.
Первым элементом массива является наше число a, следующие элементы массива вычисляются так:

  • Предыдущий элемент массива возводят в квадрат
  • Затем вычисляют остаток от деления на p
  • В нашей задачи массив будет таким:
    massive[0] = 5;
    massive[1] = 25mod7 = 4;
    massive[2] = 16mod7 = 2;
    massive[3] = 4mod7 = 4;
    massive[4] = 16mod7 = 2;
    massive[5] = 4mod7 = 4;
    massive[6] = 16mod7 = 2;

    Шаг 4
    Вычислить произведение элементов массива, которые возведены в соответствующие степени из двоичной записи числа на 1 шаге.
    Нам нужно каждый элемент массива возвести в степень (либо в первую, либо в нулевую), затем перемножить, то что получилось. Самое важное, что возводить нужно по следующему правилу:
    1 элемент массива возводится в степень последней цифры двоичного числа, 2 элемент массива возводится в степень предпоследней цифры двоичного числа и так далее.
    В нашей задаче: 50 * 40 * 21 * 40 * 20 * 41 * 21 = 16

    Шаг 5
    Вычислить остаток от деления полученного произведения.
    16mod7 = 2.
    Это значит, что наша задача 5100 mod7 = 2.

    Теперь разберем второй пример, но уже коротко.

    2 пример: 390 mod5

    Шаг 1
    9010 = 10110102

    Шаг 2
    n = 7

    Шаг 3
    massive[0] = 3;
    massive[1] = 9mod5 = 4;
    massive[2] = 16mod5 = 1;
    massive[3] = 1mod5 = 1;
    massive[4] = 1mod5 = 1;
    massive[5] = 1mod5 = 1;
    massive[6] = 1mod5 = 1;

    Шаг 4
    30 * 41 * 10 * 11 * 11 * 10 * 11 = 4

    Шаг 5
    4mod5 = 4
    390 mod5 = 4

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

    Ну а теперь мы напишем алгоритм быстрого возведения в степень на языке C++ под Visual Studio.

    #include <conio.h>
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    int main()
    {
        setlocale(LC_ALL, "Russian");
        int a(5), x(100), p(7), i(0) ;
        int vi = x; // переменная для вывода на экран
    
        int x2[30]; // создаем одномерный массив для
        while(x >= 1) // перевода в двоичную систему исчисления
        {
            x2[i] = x%2;
            x /= 2;
    	i++;
        }
        int n = i; // запоминаем количество цифр
    

    Сначала объявляем переменные, необходимые для алгоритма, а затем осуществляем перевод из десятичной системы в двоичную и считываем в переменную n количество цифр в двоичной записи.

    
        int *arr = new int[n]; // массив значений
        arr[0] = a; // 1 элемент
        for(int i = 1; i < n; i++ ) {
            arr[i] = (arr[i-1]* arr[i-1])%p; 
        }
        int proizv = 1;
        for(int j = 0; j < n; j++) {
            if (x2[j] > 0){
                proizv*= x2[j]* arr[j];
    	}
        }
        cout << "Остаток от деления " << a << "^(" << vi << ")mod" << p << " равен: " << proizv%p << endl;
        delete [] x2;
        delete [] arr;
        _getch(); // 
        return 0;
    }
    

    Сначала заполняем наш массив, вычисляя последовательно элементы. Затем вычисляем произведение и остаток от деления.

    На этом мы закончим, если у вас возникли вопросы, то оставляйте их в комментариях.
    Скачать исходник

    Опубликовано вC++

    Будьте первым, кто оставит комментарий

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

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