Возвести в степень (по модулю) + большие числа

Возвести в степень

Возвести число
в степень

по модулю

с решением

Вычислить Очистить поля
❓Инструкция

📘 Алгоритм быстрого возведения в степень онлайн с решением по модулю и без модуля. Функциональность поддерживает работу с большими числами.


ℹ Использование:

✔ Заполняем необходимые данные целыми числами, отвечая на вопросы формы.
✔ Жмем кнопку вычислить и получаем результат.

 

ℹ Галочка «по модулю» позволяет указать модуль, по которому необходимо возводить в степень.
ℹ Галочка «с решением» позволяет получить этапы вычисления: каким образом число возводилось в степень.


‼ Ограничения калькулятора:

! Максимальное число, которое можно возвести в степень — 1 000 000.
! Максимальная степень, в которую можно возвести — 5000.
! Модуль может быть довольно-таки большим, до 100 символов в числе. [1; 10e100)

📖 Теория

Алгоритм быстрого возведения в степень (по модулю).

📌 Одним из основных действий арифметики вычетов, возникающих, например, в криптографии, является вычисление ах (mod m), то есть нахождение такого у, что

где a, x, m — натуральные числа. Далее считаем, что a < m. Запись у = b (mod m) означает, что у ≡ b (mod m) и 0 ≤ у < m, т.е, y — наименьший неотрицательный вычет по модулю m, лежащий в том классе, что и b.

📎 Если вычислять «в лоб», т.е. последовательно находить (приводим формулы по модулю):

то нужно выполнить (x — 1) умножение в кольце Zm, Если n — количество разрядов в двоичной записи х, то число умножений не меньше, чем 2n-1.

 

📌 Лемма 1: Пусть x, m, a  ∈ N. Пусть x = (x0x1 … xn-1)2 т.е.

Определим целые аj по реккурентным формулам

📌 Алгоритм (быстрого возведения в степень). Даны натуральные a, m и x = (xn-1xn-2 … x0)2. Нужно вычислить y = ax (mod m),

1. Вычисляем aj (0 ≤ j ≤ n — 1) по формулам (2),

2. Вычисляем y = a0x0 a1x1 …  an-1xn-1 (mod m).

 

📌 Лемма 2. Пусть n — число разрядов в двоичной записи x. Тогда, приведенный выше алгоритм требует выполнения не более, чем, 2(n -1) умножений в кольце Zm

➕ Примеры

📍 Пример 1. Возведем число 250 без модуля.

✔ 10010 = 1100102 , считаем длину в двоичной записи n = 6. Следовательно, нам надо посчитать a1 … a6 по формулам 2 из теории.

✔ a1 = 2; a2 = 2= 4, a3 = 42 = 16, a4 = 162 = 256, a5 = 2562 = 65536, a6 = 655362 = 4294967296

✔ x1 = 0, x2 = 1, x3 = 0, x4 = 0, x5 = 1, x6 = 1 — двоичная запись в обратном порядке (от младших разрядов к старшим).

✔ Перемножаем ai-ые по второй формуле пункта 2. Другими словами, перемножаем между собой те ai-ые, у которых на соответствующей позиции в двоичной записи степени стоят единицы — это a2, a5 и a6;

✔ 250 = 4 * 65536 * 4294967296 = 1125899906842624

 

📍 Пример 2. Возведем число 250 по модулю 100. Все аналогично, только считаем ai-ые и произведения ai-ых по модулю 100.

✔ 10010 = 1100102 , считаем длину в двоичной записи n = 6. Следовательно, нам надо посчитать a1 … a6 по формулам 2 из теории.

✔ a1 = 2; a2 = 2= 4, a3 = 42 = 16, a4 = 162 = 56, a5 = 562 = 36, a6 = 362 = 96 по модулю 100

✔ x1 = 0, x2 = 1, x3 = 0, x4 = 0, x5 = 1, x6 = 1 — двоичная запись в обратном порядке (от младших разрядов к старшим).

✔ Перемножаем ai-ые по второй формуле пункта 2. Другими словами, перемножаем между собой те ai-ые, у которых на соответствующей позиции в двоичной записи степени стоят единицы — это a2, a5 и a6;

✔ 250 = 4 * 36 * 96 = 24 по модулю 100.

ℹ Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.

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

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