幂模运算

求 a^b% m 的值，有这几种方法：

一、因为 a % m = r

所以 a = mk + r

同乘b，得a*b = mkb + rb

则 a* b % m = (mkb + rb) % m = r*b % m = (a % m)*b % m = b*(a % m) % m，

　　即：(a*b) % m = (b*(a % m)) % m

　　　根据这个公式，得：a^b % m = (a * (a^b-1 % m)) % m

　然后开始递归：

function recursionMod(a, b, m) {
    /*
        根据公式: (a*b) % m = (b * (a % m)) % m 递归
        a:5 b:15 m:6 result: 5
     */
    if (b == 1) {
        return a % m
    }
    return (a * arguments.callee(a, b - 1, m)) % m
}

　　迭代的版本：

function iterationMod(a, b, m) {
    /*
        非递归版本
     */
    var result = 1
    for(var i = 0 ; i < b; i++) {
        result = (a * result) % m
    }
    return result
}

二、先证明 (a * b) % m = (a % m) * (b % m) % m

　　证明过程：

　　　　设 a = k1 * m + r1b = k2 * m + r2

则: a * b = k1 * m * k2 * m + k1 * m * r2 + k2 * m * r1 + r1 * r2

　　　　则 (a *b) % m = (r1 * r2) % m = (a % m) * (b % m) % m，得证.

　　于是，对于a¹⁷% m，有如下过程：

　　a¹⁵% m = (a % m) * ( a¹⁴ % m) % m

a¹⁴ % m = (a^₇ % m) * (a⁷ % m) % m

a⁷ % m = (a % m) * (a⁶ % m) % m

a⁶ % m = (a³ % m) * (a³ % m) % m

　　a³ % m = (a % m) * (a² % m) % m

　　a² % m = (a % m) * (a % m) % m

可以看出，相比方法一，循环次数最多可以降低到幂数b的一半。为什么说是最多，因为有的数要多于幂数b的一半，比如说5：

　　a⁵% m = (a % m) * ( a⁴ % m) % m

a⁴ % m = (a % m) * (a³ % m) % m

a³ % m = (a % m) * (a² % m) % m

　　a² % m = (a % m) * (a % m) % m

循环了四次。

代码实现如下：

function halfIterationMod(a, b, m) {
    var result = 1
    while (b>0) {
        if (b % 2 == 0) {
            a = a * a % m
            b = b / 2
        }
        else {
            result = result * a % m
            b = b - 1
        }
    }
    return result
}

三、对于a^b% m，对于任意正整数b，b的二进制表示为：

　　b = b_o* 2⁰ + b₁* 2¹ + ......+ b_n-1* 2^n-1，n为二进制位数

　　所以，a^b % m = a^{(b_o* 2^0 + b₁* 2^1 + ......+ b_n-1* 2^(n-1)) % m}

　　　　　　 = (a^{b₀ * 2^0} % m) * (a^{b₁ * 2^1} % m) * ..... * (a^{b_n-1* 2^(n-1)} % m) % m

　　而对于任意一项：a^{b_i * 2^i，}都有：

　　　　a^{b_i * 2 ^ i} % m = a^b_i ^{* 2 ^ (i-1)} * a^b_i ^{* 2 ^ (i-1)} % m

　　　　　　　　 = (a^{b_i * 2^(i-1)} % m) * (a^{b_i * 2^(i-1)} % m) % m

　　　　　　　　 = ( (a^b_i)^{2^(i-1)} % m ) * ( (a^b_i)^{2^(i-1)} % m ) % m

　　　　　　　 = ( b_i * (a^{2^(i-1)} % m) ) * ( b_i * (a^{2^(i-1)} % m) ) % m

　　　　　　　　 = b_i * ( a^{2^(i-1)} % m ) * ( a^{2^(i-1)} % m ) % m

　　　　即：a^{b_i * 2 ^ i} % m = b_i * ( a^{2^(i-1)} % m ) * ( a^{2^(i-1)} % m ) % m

系数b_i的值为0时，a^{b_i * 2^i}是1，a^{b_i * 2^i}% m = 1 不参与最终的计算。

值为1时，a^{b_i * 2 ^ i} % m 的值是前一项的平方，再取模。

代码实现如下：

function shiftMod(a, b, m) {
    var result = 1
    var base = awhile (b) {
        if (b & 1) {
            result = result * base % m
        }
        base = base * base % m
        b = b >>> 1
    }
    return result
}

测试

测试代码：

var a = 23, b = 23, m = 5

var dateNow = new Date()
var t = recursionMod(a, b, m)
console.log("结果:", t, " 递归cost:", new Date().getTime() - dateNow.getTime())

dateNow = new Date()
t = iterationMod(a, b, m)
console.log("结果:", t, " 全循环迭代cost:", new Date().getTime() - dateNow.getTime())

dateNow = new Date()
t = halfIterationMod(a, b, m)
console.log("结果:", t, " 半循环cost:", new Date().getTime() - dateNow.getTime())

dateNow = new Date()
t = shiftMod(a, b, m)
console.log("结果:", t, " 蒙哥马利cost:", new Date().getTime() - dateNow.getTime())