快速模取幂算法

2019-04-13 17:24发布

站内文章 / 模拟电子
15029 0 1129
1,乘法模运算规则:
(a * b) % n = (a % n * b % n) % n
2,模取幂运算a^b mod c:
b如果比较大,可以利用所谓的二分法,b=b0+b1*2^1+b2*2^2+...+bn*2^n从最低位b0开始，由右至左逐位扫描.
3,实例代码:

#include
using namespace std;

//计算a^bmodn
int modexp(int a,int b,int n)
{
int ret=1;
int tmp=a;
while(b)
{
//基数存在
if(b&0x1) ret=ret*tmp%n;
tmp=tmp*tmp%n;
b>>=1;
}
return ret;
}

int main()
{
cout< return 0;
}

热门文章