Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023875
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: WINDOWS

2010-04-08 16:41:35


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

这里介绍三种计算模幂的方法:效率当然是越来越高效。
方法一、straightforward method
   直接先计算b^e, 然后再mod m。
方法二、
  
按如下步骤计算:
  1. Set c = 1, e' = 0.
  2. Increase e' by 1.
  3. Set c \equiv (b \cdot c) \pmod{m}.
  4. 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
 

阅读(3274) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~