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

作为步骤。