原文地址:快速幂与快速模幂作者:张万辉 3 ^ 999 = 3 * 3 * 3 * ... * 3 直接乘要做998次乘法.但事实上可以这样做: 3 ^ 2 = 3 * 3 3 ^ 4 = (3 ^ 2) * (3 ^ 2) ...... 3 ^ 256 = (3 ^ 128) * (3 ^ 128) 3 ^ 512 = (3 ^ 256) * (3 ^ 256) 再相乘: 3 ^ 999 = 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1) = (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3 这样只要做16次乘法. 把999转为2进制数:,其各位就是要乘的数. 1 1 1 1 1 0 0 1 1 1 9 8 7 6 5 4 3 2 1 0 对应的位置号是k就是3^(2^k) 模取幂运算 计算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, res alt = 1; i = 0; while(b)把b化成2进制 { digit[i] = b%2; b = 1; } 计算(a^b) mod c for(k = i-1; k = 0; k--) { res alt = (res alt * res alt) % c; if(digit[k] == 1) { res alt = (res alt * a) % c;  } } ret rn res alt; } 这是蒙哥玛利模幂算法 模幂运算是rsa 的核心算法,最直接地决定了rsa 算法的性能.针对快速模幂 运算这一课题,西方现代数学家提出了大量的解决方案,通常都是先将幂模运算转 化为乘模运算.