【Information|RSA | 模重复平方算法 | C语言实现】
文章图片
#include
/******************************************************************************
模重复平方计算法
博文网址 http://blog.csdn.net/yxtxiaotian/article/details/52464496
幂模算法（模重复平方算法），时间复杂度O(log(n))来实现。
应用：“求b的n次方 模m”，用于RSA加解密算法中求解幂模。
******************************************************************************//******************************************************************************
“求b的n次方 模m”（递归实现）
递归公式：
b^n (mod m) = b* (b^(n-1) (mod m)) (mod m)
******************************************************************************/int powerModRec(int b, int n, int m)
{
if(0==n)
return 1;
return b*powerModRec(b, n-1, m)%m;
}/*“求b的n次方 模m” （非递归实现-->幂模算法）
*/
int powerMod(int b, int n, int m)
{
printf("输入的底数为b=%d，指数为n=%d，模为m=%d\n", b, n, m);
// a存放计算结果，初始化为1.
int a=1;
int i, k=0, num=n;
/*计算指数的二进制位数k.
*/
while(num)
{
num = num>>1;
++k;
} // 也可以将指数的二进制用一个数组或队列存放，方便取值.
for(i=0;
i>i)&1)
a = a*b %m;
b = b*b %m;
} return a;
}int main()
{
printf("分别输入底数b，指数n和模m的值：");
int b, n, m;
scanf("%d%d%d", &b, &n, &m);
//b=188, n=47, m=589;
printf("输入的底数为b=%d，指数为n=%d，模为m=%d\n", b, n, m);
int result = 0;
result = powerModRec(b, n, m);
printf("递归：b^n (mod m) = %d\n", result);
result = powerMod(b, n, m);
printf("非递归：b^n (mod m) = %d\n", result);
return 0;
}
推荐阅读
- Spring|SpringSecurity--自定义登录页面、注销登录配置
- android|逆向工程之表达式优化识别(5)-取模
- Network|Xiang Li
- Information|实验吧 后台登录writeup
- Web|由浅入深理解PHP反序列化漏洞
- Information|入侵检测基础知识