有人知道如何从数学角度证明结果'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 

作为步骤。