來源：超時代軟件 更新時間：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 快速指數算法的結果
一鍵拔號
咨詢客服
服務熱線