\[\begin{align} & x^y \pmod{n} \\ & y=\sum_{i=0}^{k} y_{i} \cdot 2^i = y_{k} \cdot 2^k +y_{k-1} \cdot 2^{k-1} + \dots + y_{1} \cdot 2^1 + y_{0} \cdot 2^0 \end{align}\]

由此，我们可以写出:

def power_mod_rtl(base, exp, mod):
	res = 1
	while exp:
		if exp & 1:
			res = (res * base) % mod
		base = (base * base) % mod
		exp >>= 1
	return res

这种就是按照等式来的，由此，算法的正确性易得

---

def power_mod_ltr(base, exp, mod):
	res = 1
	exp_bin = bin(exp)[2::]
	for bit in exp_bin:
		res = (res * res) % mod	
		if bit == '1':
			res = (res * base) % mod
	return res

但是这个算法和上面有所不同，单看算法我无法理解算法的正确性

我尝试写下如下简单的证明:

\[b^e \pmod{n}\]

当 e=1 时，易得上述算法的正确性

假设当 e=2k 时, left-to-right 的算法正确性成立

因为当 e=2k 时，e 化为二进制，最后一位必定是 0

\[b^e = b^{2k} = \prod_{i=1}^{k+1} b^{e_{i} \cdot 2^{i}} \cdot b^0\]

接下来，证明，当 e=2k+1 时,

\[b^{2k+1} = b^{2k} \cdot b \implies \begin{cases} b^{e=2k} \pmod{n}\\ b \pmod{n} \\ \end{cases}\]