如果你必須實現以下計算:如何正確使用PowMod?
什麼來實現它的正確方法?
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
如果你必須實現以下計算:如何正確使用PowMod?
什麼來實現它的正確方法?
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
最後% p
當然是必需的,否則你可能會得到比p
大得多的結果。
b^-c
在這種背景非常不正確的,因爲它沒有辦法知道,這是一個模冪,不像正指數,是不是隻是一個性能問題,而是正確性問題,也是:正常的負指數給出一個分數結果,這在這裏沒有意義。
通過消除,留下只有你最後的建議:
(powmod(b,-c,p) * powmod(g,s_3, p)) % p
(a * b) % c = ((a % c)*(b % c)) % c
所以,
(b^-c * g^s_3)) % p = ((b^-c % p)*(g^s_3 % p)) % p
g^s_3 % p
和b^-c % p
應使用powmod
來解決。 powmod的正確實施取決於你。
How to deal with negative exponents in modular arithmetic?可能會幫助你。
取決於是否powmod
可以處理負指數,最後一個是正確的。前兩個具有不可解釋的b^-c
(或者它被解釋爲對位序列的操作),第三個可能具有大於p
的結果,因爲兩個餘數的乘積可以大到(p-1)^2
。
要獲得負指數權使用費馬小定理:
任何黃金
p
和a%p!=0
一個具有a^(p-1)%p==1
。
,這樣完整的計算是
(powmod(b, p-1-(c%(p-1)),p) * powmod(g,s_3,p)) % p
(A * B)%C =((A%C)*(B%C))%C –
可以將您的'powmod'處理負指數? – LutzL
@LutzL aw我什至沒有想到這一點。它似乎不能 – user66875