2017-03-16 283 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