首页 > 代码库 > 快速模取幂
快速模取幂
数论计算中经常出现的一种运算就是求一个数的幂ab对另外一个数n个模的运算,即计算:
ab mod n (a,b,n是正整数)
由于计算机只能表示有限位的整数,所以编程时模取幂的运算要注意值的大小范围,当ab的值超过整数范围时,mod运算便无法进行。
如何解决这个问题,我们引出一个能计算ab mod n的值的有用算法——反复平方法,首先我们必须明确:
d=ab mod n=(…((((a mod n)*a)mod n)*a)mod n…*a)mod n {共b个a}
由此可以引出一个迭代式
d:=a;
for i:=2 to b do
d:=d mod n*a;
d:=d mod n;
时间复杂度为O(b),当b很大时,效率很低。我们可以将b转换为二进制数<bk,bk-1,...,b1,b0>,然后从最低位b0开始,由右至左逐位扫描,每次迭代时,用到下面两个恒等式:
a2c mod n =(ac)2 mod n bi=0
a2c+1 mod n =a*(ac)2 mod n bi=1 (0<=c<=b)
其中c为b的二进制数的后缀(bi-1...b0)对应的十进制数,当c成倍增加时,算法保持d=ac mod n不变,直至c=b。
LL fun(LL x,LL n,) { LL res=1; while(n>0) { if(n & 1) res=(res*x)%Max; //二进制位为1时执行此步 x=(x*x)%Max; n >>= 1; //实质上这步只是不断地使二进制位从右向左移动,实现的是使res乘的A值等于2^(对应位+1) } return res; }
快速模取幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。