服務(wù)熱線4000-656-360
來源：超時代軟件 更新時間：2014年05月11日 19:03:06
作者：鄢喜愛 楊金民 田華
RSA 中的加密和解密過程都為求一個整數(shù)的整數(shù)次冪。如果按其含義直接計算, 則中間結(jié)果運(yùn)算量非常大, 運(yùn)算速度慢, 且有可能超出計算機(jī)所允許的整數(shù)取值范圍。如果利用模運(yùn)算性質(zhì): ( a* b) mod n= [ (a mod n) * (b mod n) ] modn, 就可以減小中間結(jié)果, 提高運(yùn)算速度。
求a的m次方mod n 可按如下步驟進(jìn)行, 其中a, m 是正整數(shù)。
首先將 m 表示成二進(jìn)制形式bk , bk- 1, ,,b0 , 然后按如下快速指數(shù)算法進(jìn)行:
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 是指數(shù); d 是中間結(jié)果;return d 為*終所求的結(jié)果。
例3: 求上面實例中的123的103次方mod 143。
將103 表示為 1100111, 算法的演示過程見表2, 得出123的103次方mod 143= 85。
表2 快速指數(shù)算法的結(jié)果
一鍵拔號
咨詢客服
