快速指数取模的实现算法
转自：
http://blog.csdn.net/lzyblog/archive/2006/10/26/1351436.aspx
由于一个整数的指数结果很大，可能远远超出计算机处理范围，故必须简化计算方式．这里采用快速取模方法.
原理为：在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<c,其它不用a<c.条件2:ac互素
{
_int64 l[
500
],z
=-
1
,y;
for
(;b
!=
1
;b
>>=
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;
}