算法——指数取模运算（蒙哥马利算法）

2019-04-13 15:05发布

站内文章 / 模拟电子
11291 0 964

蒙哥马利算法简介

蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法，是RSA加密算法的核心之一。——百度百科
题目来源——xdoj1372

用到的公式

(a * b) % p = a % p * b % p % p

推论

base^exp % p = （base % p） * （base % p） * … *（base % p） % p（总共exp个小括号） 若为exp偶数 = （base^2 % p) * (base^2 % p) * … * (base^2 % p) % p （总共exp/2个小括号） 若exp奇数 = （base^2 % p) * (base^2 % p) * … * (base^2 % p) * base % p % p（总共（exp-1）/ 2个小括号） …… 然后一直指数减半，底数平方取模。最后得出答案。

c语言实现

#include long long int base;//底数 long long int exp_1;//指数 long long int mod;//取模数 long long Montgomery() { long long int res = 1; while(exp_1) { if (exp_1&1)//如果为奇数 res = (res*base) % mod; exp_1 >>= 1;//指数对半 base = (base*base) % mod;//底数平方 } return res; } int main() { scanf("%I64d%I64d%I64d", &base, &exp_1, &mod); printf("%I64d", Montgomery()); return 0; }
样例输入
2 10000 10007
样例输出
3909

结语

蒙哥马利算法极大地减少了运算量，并且使得数据规模极大减小。使原本看似不可能完成的程序变得可行。