2017-03-16 39 views
1

如果你必須實現以下計算:如何正確使用PowMod?

enter image description here

什麼來實現它的正確方法?

b^-c * powmod(g,s_3, p) 

(b^-c * powmod(g,s_3, p)) % p 

powmod(b,-c,p) * powmod(g,s_3, p) 

(powmod(b,-c,p) * powmod(g,s_3, p)) % p 
+0

(A * B)%C =((A%C)*(B%C))%C –

+0

可以將您的'powmod'處理負指數? – LutzL

+0

@LutzL aw我什至沒有想到這一點。它似乎不能 – user66875

回答

3

最後% p當然是必需的,否則你可能會得到比p大得多的結果。

b^-c在這種背景非常不正確的,因爲它沒有辦法知道,這是一個模冪,不像正指數,是不是隻是一個性能問題,而是正確性問題,也是:正常的負指數給出一個分數結果,這在這裏沒有意義。

通過消除,留下只有你最後的建議:

(powmod(b,-c,p) * powmod(g,s_3, p)) % p

1

取決於是否powmod可以處理負指數,最後一個是正確的。前兩個具有不可解釋的b^-c(或者它被解釋爲對位序列的操作),第三個可能具有大於p的結果,因爲兩個餘數的乘積可以大到(p-1)^2

要獲得負指數權使用費馬小定理:

任何黃金pa%p!=0一個具有a^(p-1)%p==1

,這樣完整的計算是

(powmod(b, p-1-(c%(p-1)),p) * powmod(g,s_3,p)) % p