来源：超时代软件 更新时间：2014年05月11日 19:03:06
作者：鄢喜爱 杨金民 田华
RSA 中的加密和解密过程都为求一个整数的整数次幂。如果按其含义直接计算, 则中间结果运算量非常大, 运算速度慢, 且有可能超出计算机所允许的整数取值范围。如果利用模运算性质: ( a* b) mod n= [ (a mod n) * (b mod n) ] modn, 就可以减小中间结果, 提高运算速度。
求a的m次方mod n 可按如下步骤进行, 其中a, m 是正整数。
首先将 m 表示成二进制形式bk , bk- 1, ,,b0 , 然后按如下快速指数算法进行:
c= 0;d= 1
for ( i= k; i< = 0; i- - )
{ c= 2* c;
d= (d* d) % n;
if ( bi= = 1)
{
c= c+ 1;
d= ( d* a) % n;
} }
return d
其中, c 是指数; d 是中间结果;return d 为*终所求的结果。
例3: 求上面实例中的123的103次方mod 143。
将103 表示为 1100111, 算法的演示过程见表2, 得出123的103次方mod 143= 85。
表2 快速指数算法的结果
一键拔号
咨询客服
服务热线