Я изучал эту ссылку из Википедии по модулю большого числа. Вот псевдокод.
function modular_pow(base, exponent, modulus)
result := 1
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base = (base * base) mod modulus
return result
Я не понимаю объяснение, данное в вики. Почему я должен проверять, является ли exp%2 четным или нечетным. также почему я делаю три операции?
Этот алгоритм представляет собой комбинацию алгоритма возведение в степень путем возведения в квадрат и арифметики по модулю. .
Чтобы понять, что происходит, сначала рассмотрим ситуацию, когда exponent является степенью 2. Затем, предполагая, что exponent = 2 ^ k, результат можно вычислить, возведя результат в квадрат k раз, т.е.
res = (...((base ^ 2) ^2 ) ... ) ^2))
---------------------
k times
Когда exponent не является степенью 2, нам нужно сделать дополнительные умножения. Оказывается, если мы можем разделить exponent на 2 без остатка, мы можем возвести в квадрат основание и разделить показатель степени. Если же есть остаток, мы должны дополнительно умножить промежуточный результат на значение текущего base.
То, что вы видите, это то же возведение в степень путем возведения в квадрат, примененное к умножению по модулю. Алгоритм обозначает целочисленное деление на два с использованием операции exponent >> 1, которая идентична floor(exponent / 2).
