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

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

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

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

 

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

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

 Максимальное число, которое можно возвести в степень — 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) умножение в кольце Z_m, Если n — количество разрядов в двоичной записи х, то число умножений не меньше, чем 2^n-1.

 

 Лемма 1: Пусть x, m, a  ∈ N. Пусть x = (x₀x₁ … x_n-1)₂ т.е.

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

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

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

2. Вычисляем y = a₀^x₀ a₁^x₁ …  a_n-1^x_n-1 (mod m).

 

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

 Пример 1. Возведем число 2⁵⁰ без модуля.

50₁₀ = 110010₂ , считаем длину в двоичной записи n = 6. Следовательно, нам надо посчитать a₁ … a₆ по формулам 2 из теории.

 a₁ = 2; a₂ = 2² = 4, a₃ = 4² = 16, a₄ = 16² = 256, a₅ = 256² = 65536, a₆ = 65536² = 4294967296

 x₁ = 0, x₂ = 1, x₃ = 0, x₄ = 0, x₅ = 1, x₆ = 1 — двоичная запись в обратном порядке (от младших разрядов к старшим).

 Перемножаем a_i-ые по второй формуле пункта 2. Другими словами, перемножаем между собой те a_i-ые, у которых на соответствующей позиции в двоичной записи степени стоят единицы — это a₂, a₅ и a₆;

 2⁵⁰ = 4 * 65536 * 4294967296 = 1125899906842624

 

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

50₁₀ = 110010₂ , считаем длину в двоичной записи n = 6. Следовательно, нам надо посчитать a₁ … a₆ по формулам 2 из теории.

 a₁ = 2; a₂ = 2² = 4, a₃ = 4² = 16, a₄ = 16² = 56, a₅ = 56² = 36, a₆ = 36² = 96 по модулю 100

 x₁ = 0, x₂ = 1, x₃ = 0, x₄ = 0, x₅ = 1, x₆ = 1 — двоичная запись в обратном порядке (от младших разрядов к старшим).

 Перемножаем a_i-ые по второй формуле пункта 2. Другими словами, перемножаем между собой те a_i-ые, у которых на соответствующей позиции в двоичной записи степени стоят единицы — это a₂, a₅ и a₆;

 2⁵⁰ = 4 * 36 * 96 = 24 по модулю 100.