模幂 modular exponentiation 的计算方法-wqfhenanxc

所谓模幂，就是计算(b^e) mod m的值。这里b、e、m都为给定的某个值。
比如计算(5^3) mod 13 或者计算 (4^13) mod 497。

这里介绍三种计算模幂的方法：效率当然是越来越高效。
方法一、straightforward method
直接先计算b^e, 然后再mod m。
方法二、
按如下步骤计算：

Set c = 1, e' = 0.
Increase e' by 1.
Set $c \equiv (b \cdot c) \pmod{m}$ .
If e' < e, goto step 2. Else, c contains the correct solution to $c \equiv b^e \pmod{m}$ .

其实就是乘一次模一次；比如按这种方法计算 (4^13) mod 497的过程如下：

e' = 1. c = (1 * 4) mod 497 = 4 mod 497 = 4.
e' = 2. c = (4 * 4) mod 497 = 16 mod 497 = 16.
e' = 3. c = (16 * 4) mod 497 = 64 mod 497 = 64.
e' = 4. c = (64 * 4) mod 497 = 256 mod 497 = 256.
e' = 5. c = (256 * 4) mod 497 = 1024 mod 497 = 30.
e' = 6. c = (30 * 4) mod 497 = 120 mod 497 = 120.
e' = 7. c = (120 * 4) mod 497 = 480 mod 497 = 480.
e' = 8. c = (480 * 4) mod 497 = 1920 mod 497 = 429.
e' = 9. c = (429 * 4) mod 497 = 1716 mod 497 = 225.
e' = 10. c = (225 * 4) mod 497 = 900 mod 497 = 403.
e' = 11. c = (403 * 4) mod 497 = 1612 mod 497 = 121.
e' = 12. c = (121 * 4) mod 497 = 484 mod 497 = 484.
e' = 13. c = (484 * 4) mod 497 = 1936 mod 497 = 445.

方法三、Right-to-left binary method
这种方法需要根据e的二进制形式进行计算。

$e = \sum_{i=0}^{n-1} a_i 2^i$

$b^e = b^{\left( \sum_{i=0}^{n-1} a_i 2^i \right)} = \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}$

$c \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}\ (\mbox{mod}\ m)$

写成C代码来描述计算过程如下：

//这里的参数base、 exponent、 modulus 分别代表上面的b、e、m。

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
 
    Bignum result = 1;
 
    while (exponent > 0) {
        if (exponent & 1) {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }
 
    return result;
}

This code