Кто-то знает, как доказать результат: a^b% m = (... ((a% m) * a)% m) ...... * a)% m 'из математического представления?

Question

Недавно я закодирован на реализованный RSA алгоритм, я был смущен проблемами MOD-POWER, я не мог, почему уравнение верно, я не могу дать доказательство этого уравнения:

'a^b % m = (...((a % m) * a) % m) ......* a) % m' 

с математической точки зрения?

Answer 1

Из основных вещей, которые мы знаем о умножении в модульной арифметике.

Мы знаем, что (a * b) % m == ((a % m) * (b % m)) % m

Answer 2

Поскольку власть определяется рекурсивно

a^0 = 1, a^b = a^(b-1) * a 

вы докажете модульную формулу также на индукцию, то есть, используя

a^b % m = ( (a^(b-1) % m) * (a % m) ) % m 

как шаг.