快速模幂算法及其证明

创建时间 2021-10-03

更新时间 2021-10-03

分类

数学理论

标签

数论

基础运算

定理一：设 $a, b \in \mathbb{Z}$ , $n \in \mathbb{N^+}$ ，则有：

$(a \cdot b) \bmod n = [(a \bmod n) \cdot b] \bmod n$

证明：设 $a \bmod n = d$ ，则有 $a = kn + d$ ， $k \in \mathbb{Z}$ ；

$\begin{aligned} (a\cdot b) \bmod n & = [b(kn + d)] \bmod n \\ & = [bkn + bd] \bmod n \\ & = bd \bmod n \\ & = [(a \bmod n) \cdot b] \bmod n \end{aligned}$

证毕；

定理二：设 $a, b \in \mathbb{Z}$ , $n \in \mathbb{N^+}$ ，则有：

$(a \cdot b) \bmod n = [(a \bmod n) \cdot (b \bmod n)] \bmod n$

证明：设：

$a \bmod n = d$ ，则有 $a = kn + d$ ， $k \in \mathbb{Z}$ ；
$b \bmod n = e$ ，则有 $b = ln + e$ ， $l \in \mathbb{Z}$ ；

$\begin{aligned} a\cdot b \bmod n & = (kn + d)(ln + e) \bmod n \\ & = [kln^2 + (ke + dl)n + de] \bmod n \\ & = de \bmod n \\ & = (a \bmod n) \cdot (b \bmod n) \bmod n \end{aligned}$

证毕；

定理三：设 $a_0, a_2, \cdots, a_m \in \mathbb{Z}$ , $n \in \mathbb{N^+}$ ，则有：

$(a_1 \cdot a_2 \cdots a_m) \bmod n = \left[\prod_{i = 0}^m (a_i \bmod n ) \right] \bmod n$

证明：和定理一类似

设 $S$ 是 $a_0, a_1, \cdots, a_m$ 的集合，则对于每个 $a_i \in S, i \in \mathbb{N}, i \leqslant m$ ；

设 $d_i = a_i \bmod n$ ，则都存在 $k_i \in \mathbb{Z}$ 使得 $a_i = k_in + d_i$

于是：

$\begin{aligned} (a_1 \cdot a_2 \cdots a_m) \bmod n =& \left[\prod_{i = 0}^m (k_in + d_i) \right] \bmod n \\ \xlongequal{多项式乘法规则}& \left(\prod_{i = 0}^m d_i \right) \bmod n \\ =& \left[\prod_{i = 0}^m (a_i \bmod n ) \right] \bmod n \end{aligned}$

定理三推论： $a^N \bmod n = (a \bmod n)^N \bmod n$

快速模幂算法

假设要计算 $b^N \bmod m$

将 $N$ 用二进制记号表示成 $N = (a_ka_{k-1} \cdots a_1a_0)_2$ ；
用逐个平方及模 $m$ 约化求出 $b, b^2, b^4, \cdots, b^{2^k}$ 模 $m$ 的最小正剩余，其中 $a^k = 1$ ；
取 $a^j = 1$ 的 $j$ 所对应的 $b^{2^j}$ 模 $m$ 的最小正剩余的乘积
再模 $m$ 约化即可；

证明：

$\begin{aligned} b^N \bmod m &= b^{(a_ka_{k-1} \cdots a_1a_0)_2} \bmod m\\ &= b^{a_{k} \cdot 2^k} \cdot b^{a_{k-1} \cdot 2^{k - 1}} \cdots b^{a_0 \cdot 2^0} \bmod m \\ &\xlongequal{定理三} \left[\prod_{i = 0}^k (b^{a_i \cdot 2^i} \bmod m) \right] \bmod m \end{aligned}$

例子：求 $2^{644} \bmod 645$

$644 = (1010000100)_2$
计算二进制位为 $1$ 的模算数：
- $2^{2^2} = 2^{4} \equiv 16 \pmod {645}$
- $2^{2^7} = 2^{128} \equiv 391 \pmod {645}$
- $2^{2^9} = 2^{512} \equiv 256 \pmod {645}$
计算乘积再求模：

$\begin{aligned} 2^{644} &= 2^{512} 2^{128} 2^4 \\ &= 256 \times 391 \times 16 \equiv 1601536 \equiv 1 \pmod {645} \\ &\xlongequal{或} (((256 \times 391) \bmod {645}) \times 16) \bmod {645} = 1 \end{aligned}$

相关 Python 代码，计算 $a^b \bmod n$

def power_modulo(a: int, b: int, n: int) -> int:

    # 利用定理三推论，保证 a <= n，降低计算复杂度
    a %= n

    value = 1
    while b:
        # 对于位为 1 的才计算
        if b & 1:
            value = (value * a) % n

        # 计算 a ** (2 ** b_k)
        a = (a * a) % n

        # 移位计算下一个
        b >>= 1

    return value

快速模幂算法及其证明

基础运算

快速模幂算法

评论