Здравствуйте, сегодня поговорим об алгоритме быстрого возведения в степень по модулю, а также реализуем этот алгоритм на 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; }
Сначала заполняем наш массив, вычисляя последовательно элементы. Затем вычисляем произведение и остаток от деления.
На этом мы закончим, если у вас возникли вопросы, то оставляйте их в комментариях.
Скачать исходник
Будьте первым, кто оставит комментарий