所谓模幂，就是计算(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-
阅读(3429) | 评论(0) | 转发(0) |
