对快速幂运算的一点思考

算法 scheme

---

大家还记得快速幂运算吗?它的用处是快速计算一个数的整数幂.它基于如下一个公式:
令a为任意实数,n为任意非负整数

$$a^n= \begin{cases} 1 & \text{if $n$ = 0} \\[2ex] (a^{\frac{n}{2}})^2 & \text{if $n$ is even} \tag0\\[2ex] a^{n-1} \cdot a & \text{if $n$ is odd} \\ \end{cases}$$

相信很多人都对快速幂运算都有所了解.同样,关于快速幂模运算,也有一个类似的方法,叫做反复平方法.它的基本思想和快速幂运算的思想一样.

关于这么个简单的算法,似乎没有什么可以说的.但,现在我们走到代数的层面上,对于一个代数结构$G$,定义在它上面的是一个二元运算(注意封闭律)$\oplus$,现在任取这个集合的任意一个元素$v$,我做如下的运算:

$$\underbrace{v\oplus ...\oplus v}_{n\text{ times}}$$
用一般的方法,当然是需要进行n次的$\oplus$运算.但,等等!这似乎可以改进啊!我们不妨构造一下如下的公式:
$$v^n= \begin{cases} e & \text{if $n$ = 0 , $e$ is the "identity element" of the operator $\oplus$ in set $G$} \\[2ex] v^{\frac{n}{2}}\oplus v^{\frac{n}{2}} & \text{if $n$ is even} \tag1\\[2ex] v^{n-1} \oplus v & \text{if $n$ is odd} \\ \end{cases}$$

但等等!这样运算真的能行吗?首先:

$$v^n=v^{\frac{n}{2}}\oplus v^{\frac{n}{2}}\\ v^n = v^{n-1} \oplus v$$ 真的正确吗!?
似乎也没有证据说明它不正确.但现在,记住,我们已经走到代数的层面上思考了,$v$不一定是个数了,也可能是一个点,一个多项式...等等.那为什么当$v$是数的时候就能保证它正确呢?我们不妨换个写法.
$$v^n=\underbrace{v\oplus ... \oplus v}_{n\text{ times}} = \underbrace{(v\oplus...\oplus v)}_{\frac{n}{2}\text{times}} \oplus \underbrace{(v\oplus...\oplus v)}_{\frac{n}{2}\text{times}} = v^{\frac{n}{2}}\oplus v^{\frac{n}{2}}$$

发现了什么了吗,结合律啊!一个代数结构,如果它的运算满足结合律,那么就把它称为半群.

OK.那么就一目了然了.关于如何证明这个(1)式,我们完全可以根据结合律的相关性质.比如:假设定义在半群$S$上的二元代数运算为$\oplus$,那么对于任意的$a_1,a_2,..,a_n \in S$有:$(i = {1,2,...,n})$

$$a_1\oplus a_2 \oplus a_3 ...\oplus a_n = [a_1\oplus ... \oplus a_i] \oplus [a_{i+1} \oplus ... \oplus a_{n}]$$
通过这个性质我们很快就能证明(1)的正确性(当n=0的那个情况,其实更多的是定义,为了使运算正确).那么接下来是构造算法.我暂时还不会在这个博客上写伪代码,我就简单描述一下:

算法1:
输入:该半群的二元运算符$\oplus$,运算次数$n$,该半群的元素$a$,该运算的单位元$e$
输出: $\underbrace{a\oplus ...\oplus a}_{n\text{ times}}$
步骤:
若$n$ = 0,返回$e$
若$n$为偶数,用算法1计算,$v = \underbrace{a \oplus ... \oplus a}_{\frac{n}{2} \text{ times}}$,然后计算$v \oplus v$并返回.
若$n$为奇数,用算法1计算$v = \underbrace{a \oplus ... \oplus a}_{n-1 \text{ times}}$,然后计算$v \oplus a$并返回.

算法结束.

下面是实现相关算法的一段scheme的代码:

;;q_power函数:a为运算的对象,n为运算的次数,identity为operator的单位元,operator为定义的运算
(define (q_power a n identity operator)  
  ;;square(平方)过程,value作为要平方的值
  (define (square value)   
    (operator value value)) ;;square定义完成
  ;;q_power函数定义:
  (cond ;;分支条件
   ((= n 0)   ;;边界条件
    identity)
   ((= (remainder n 2) 0)          ;;当n为偶数
    (square (q_power a (/ n 2) null_value operator)))
   (else        ;;当n为奇数
    (operator (q_power a (- n 1) null_value operator) a)))) ；q_power函数定义结束

(cmd markdown的scheme代码高亮效果很差,和我在emacs下的效果差太远了.凑合着看看吧...)
我选择用scheme代码,因为对于把函数作为"一等公民"的语言里,我比较熟悉的是scheme.在mit-scheme/racket作为解释器下运行没问题.

简单分析一下q_power过程的时间复杂度.首先.我们可以写出如下的递归式:
设n为输入规模(在这里其实就是运算次数),T(n)为输入规模为n时的时间复杂度,O(c)为operator操作的时间复杂度.那么

$$T(n)= \begin{cases} T(\frac{n}{2})+O(c) & \text{if n even and > 0} \\ T(n-1)+O(c) & \text{if n odd} \\ O(1) & \text{if n = 0} \end{cases}$$
不妨就考虑operator操作的时间复杂度为O(1).当n是偶数,问题规模减半.而当n是奇数,那么它的下一次调用的n-1必然是偶数,可以视为$T(n) = T(n-1) + O(1) = T(\frac{n-1}{2}) + O(1) + O(1)$.即$T(n) \le T(\lfloor{\frac{n}{2}}\rfloor) + 2\cdot O(1) = T(\lfloor{\frac{n}{2}}\rfloor) + O(1)$

同时也必然会有 $T(n) \ge T(\lfloor{\frac{n}{2}}\rfloor)+O(1)$

容易解得:

$$T(n) = O(\log n)$$
因此这个q_power过程的效率也算很高了(当operator操作为常数时间的情况下)

使用这段代码需要自己定义相关的"运算"及其"单位元".在上面那段scheme代码里就是指identity 和 operator了.

不妨测试一下代码:

;;快速计算2^11
(q_power 2 11 1 *)
;;快速计算3*10=10+10+10
(q_power 3 10 0 +)
;;运行结果
;;>>> 2048
;;>>> 30
;;加法模定义
(define (plus-mod m)
  (lambda (x y)
    (remainder (+ x y) m)))
;;乘法模定义
(define (mod_power m)
  (lambda (x y)
    (remainder (* x y) m)))
;;计算 3*13 mod 10
(q_power 3 13 0 (plus-mod 10))
;;计算 2^13 mod 159
(q_power 2 13 1 (mod_power 159))
;;运行结果
;;>>> 9
;;>>> 83

当然,比较简单的也就这些了.其实关于椭圆曲线(ECC)的点运算.一样可以用这个算法(实际上在ECC加密上称为double-and-add算法),因为椭圆曲线的点运算满足结合律嘛.

当然,像这种东西,不过就是拿出来再思考一下罢了,理论价值实际上并不大.因为就算不需要这样的思考,一样能够写出相关的算法.但是思考这种东西,有时候并不为什么实际,只不过是有点意思罢了哈哈