RSA中的模幂运算之平方乘算法的递归与非递归实现

2019-04-13 12:12发布

站内文章 / 模拟电子
12698 0 1798
具体原理不多说，直接上代码实现，要注意的地方就是递归方式中结果的类型要定义为unsigned long long 防止溢出，比如这里测试的例子（9726^{3533} mod 11413），如果结果的类型为unsigned（32位），比如本例运算变量result在循环过程中有一中间值为9726^{3}，超过32位，就会产生溢出。 #include using namespace std; //如果将mod理解成无限大，那么就相当于是在求指数，既然放大是合理的那么缩小当然也是合理的,即在循环的过程中对result和a求模不会影响最终的结果同时减小运算量 //非递归快速幂 unsigned none_recur_pow_mod(unsigned a, unsigned b, unsigned mod) { unsigned result = 1; while (b) { if (b & 1) { result = (result*a) % mod; } a = (a*a) % mod; b >>= 1; } return result; } //递归快速幂（这里是将间递归快速幂改写成“非递归形式”，但原理仍然是递归的思想） unsigned recur_pow_mod(unsigned a, unsigned b, unsigned mod) { unsigned long long result = 1; //这里result定义为64位的整型是因为有时result的中间值会超过32位，如果只用unsigned会溢出 unsigned array[64] = { 0 }; //用来存储b的二进制形式的每一位数 unsigned length = 0; while (b) { array[length++] = b & 1; b >>= 1; } for (int j = length - 1; j >= 0; j--) { if (array[j] == 1) result = (result * result*a) % mod; else result = (result * result) % mod; } return result; } int main() { unsigned a, b, mod; unsigned result = 0; cin >> a >> b >> mod; result = none_recur_pow_mod(a, b, mod); cout <<"none recursive: " << result << endl; result = recur_pow_mod(a, b, mod); cout << "recursive: " << result << endl; return 0; }

热门文章