求一个高效的指数取模运算算法

Question

求一个高效的指数取模运算算法

Answer 1

由于一个整数的指数结果很大,可能远远超出计算机处理范围,故必须简化计算方式．这里采用快速取模方法.原理为：在4的5次方运算中,5能够化作2*2+1,这是因为5的2进制数为101．所以4的5次方运算便能写作((4)^2*1)^2*4,其中1表示的是4的0次方,^2表平方．再运用模的性质：(a*b)mod(m)=(amod(m)*bmod(m))mod(m),所以（4^5）mod(m)可先化为（((4)^2*1)^2*4）mod(m),再化为（((4)^2mod(m)*1)^2mod(m)*4）mod(m)．举例子－－（4^5）mod(3)＝（((4)^2*1)^2*4）mod(3)＝（(1*1)^2mod(3)*4）mod(3)=（1*4）mod(3)＝1．该函数运行方式取于上述算法思想,首先将幂分解成2进制数,得到一个从幂的最低位数开始01组成的栈：分解b为2进制数．记录下分解成的位数z,构造栈
for(;b!=1;b>>=1)
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;｝
然后出栈进行＂（a^b）mod(c)＂的运算．这里用栈的原因是为了使幂的2进制数排列倒过来,实现最高位上的2进制数能够循环它的位数次,最低位上的2进制数只循环一次．每次的循环得到平方取模的值,一直到结束,取得一个值,即（a^b）mod(c)．
for(;z>0;z--)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最后次模
return y;
这是一个比较快的运算方法.
完整源程序：
//指数取模:a的b次方modc=x
_int64 mod(_int64 a,_int64 b,_int64 c)//(a)^bmod(c)//条件1：在rsa中a=1)//分解b为2进制数．记录下分解成的位数z,构造栈l
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;
}
//a%=c;//如果一开始数就很大,先模一次,防止过大,求逆
y=a*a%c;//第一次模
for(;z>0;z--)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最后次模
return y;
}
C#改写的,在vs.net 2005下调试通过：
///
/// 指数取模:x=(a^b)%c （a的b次方mod）
/// 条件1：在rsa中a= 1)//分解b为2进制数．记录下分解成的位数z,构造栈l
{
z++;
if (b % 2 == 0)
l[z] = 0;
else
l[z] = 1;
}
//a%=c;//如果一开始数就很大,先模一次,防止过大,求逆
y = a * a % c;//第一次模
for (; z > 0; z--)
{
if (l[z]>0) y = (y * a % c) * (y * a % c) % c;
else y = y * y % c;
}
if (l[0]>0) y = (y * a % c);//最后次模
return y;
} (参考百度）