如果你必须实现以下计算:如何正确使用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