[转]模取幂运算 (a^b mod c)

2019-04-13 21:00发布

站内文章 / 模拟电子
17211 0 1351
  [转][算法] 模取幂运算 (a^b mod c) 计算机   2009-04-17 21:36   阅读26   评论0   字号： 大  中  小 转自：http://blog.csdn.net/dremi/archive/2007/04/17/1568221.aspx 这个算法的思想我是从一本书上看到的，对合法的输入能很快的计算出结果来，其思想是利用 数学公式： (a * b ) mod c = (( a mod c) * b) mod c; 首先把 b 转化成二进制如： b0 b1 b2 b3..... b31 即 b ＝ b0*231 + b1*230+......+ b31; 也就是把 ab  =  a ^ (b0*231 + b1*230+......+ b31)  ＝ [a(b0*2^31)]  * [a(b1*2^30)] *..... * [ab31*2^0]; 所以如果b的化成二进制的某位为0时，可以直接用这样算 resualt ＝ （resualt * resualt）%c; 若为1 则为 resualt = ( resualt * a) % c; 例如：35 mod 4 ; 5转化成二进制为101，即35 = 3(2^2) *   3(2^0) = 34 * 31 所以35 mod 4 = 34 * 3 mod 4 = ((34)mod 4 * 3)mod 4; 31 mod 4 = 3, 32 mod 4 = (31  * 3 1) mod 4 ; 34 mod 4 = (32 *32)mod 4;   代码如下： /****************************************************/
//       模取幂运算 计算a^b mod c
//       利用公式  
//       (a*b)mod(c) = ((a mod c )*b)mod c
/****************************************************/
int a_b_Mod_c(int a, int b, int c)
{//前提 a b c 都是正数
    int digit[32];
    int i, k, resualt = 1;
    i = 0;
    while(b)//把b化成2进制
    {
        digit[i++] = b%2;
        b >>= 1;
    }
    //计算(a^b) mod c
    for(k = i-1; k >= 0; k--)
    {
        resualt = (resualt * resualt) % c;
        if(digit[k] == 1)
        {
            resualt = (resualt * a) % c;
        }
    }     return resualt;
}

热门文章