数论与群论密码学-05-快速幂算法

考察如下运算的复杂度:

\[ a^n = \prod_{i=1}^n a = \underbrace{a \times \cdots \times a}_{\text{$n$ 个 $a$}} \]

我们可以观察到,以累乘的方法计算幂需要进行 \(\Theta(n)\) 个乘法运算。即使不考虑到逐次的积的数位会以线性的方式递增,该算法也并非是多项式时间可算的。

以下给出更高效的快速幂算法。

快速幂算法

若我们将指数进行二进制展开,有

\[ \begin{aligned} n &= e_02^0 + e_12^1 + \cdots + e_k2^k\\ &= \sum_{i=0}^k e_i2^i\\ &= \sum_{i=0\\e_i \ne 0}^k 2^i \end{aligned} \]

其中 \(e_i \in \{0, 1\}, k-1 = \lfloor log_2(n) \rfloor\)

因此有

\[ a^n = a^{\sum 2^i} = \prod_{i=0\\e_i \ne 0}^k a^{2^i} \]

若我们令 \(a_i = a^{2^i}\),则有

\[ a^n = \prod_{i=0\\e_i \ne 0}^k a_i \]

注意到有 \(a_i = (a_{i-1})^2\)

\(\displaystyle b_i = \prod_{i=0\\e_i \ne 0}^i a_i\)\(b_k = a^n\)

于是有如下算法:

\(a_0 := a, b_{-1} := 1, n_0 := n\)
对于 \(i := 0 : k\) (相当于 当 \(n_i \ne 0\)
\(\qquad n_i := \lfloor \frac{n_{i-1}}{2} \rfloor\)
\(\qquad a_i := (a_{i-1}^2)\)
\(\qquad b_i := \begin{cases} a_ib_{i-1}, &\text{若 $n_i$ 为奇数} \\ b_{i-1}, &\text{若 $n_i$ 为偶数} \end{cases} \iff \begin{aligned} r_i &:= n_i \bmod 2;\\ b_i &:= b_{i-1}a_i^{r_i} \end{aligned}\)

此时 \(b_k = a^n\).

因此我们至多需要进行 \(2k\) 个乘法运算(\(k\) 次迭代中每一次至多需要为 \(a_i\)\(b_i\) 分别进行一次乘法运算)。因此该算法需要进行 \(\Theta(log(n))\) 而非原先的 \(\Theta(n)\) 次乘法运算。

模幂运算

若我们在 \(\mathbb{Z}/m\mathbb{Z}\) 中计算幂,可以在每一轮迭代中分别取一次模:

\[ a_i = rem(a_{i-1}^2, m), b_i = rem(b_{i-1}a_i^{r_i}, m) \]

使用了快速幂算法的模幂运算复杂度为 \(\Theta(log(n)log^2(m))\).

如快速幂一样,模幂运算共需要进行 \(\Theta{log(n)}\) 次乘法运算。由于每一个 \(a_i, b_i\) 的位数都不会超过 \(m\),因此每一次乘法运算至多需要 \(\Theta(log^2(m))\) 次位运算。