有人知道如何從數學角度證明結果'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 

作爲步驟。