指数模运算🤔

\[ \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} \]