我们如何在模块化上下文中使用带有负指数的pow
?
pow(x, y, [z]) If z is present, x and y must be of integer types, and y must be non-negative.
>>> pow(11444, -357)
0.0
>>> pow(11444, -357) % 48731
0.0
>>> pow(11444, -357, 48731)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: pow() 2nd argument cannot be negative when 3rd argument specified
在我的用例中,我想使用 Schnorr 方案加密消息:
y = (g ** -w) mod p
但是 pow
不会接受负数作为此处的第二个参数。例如,来自
g = 11444
p = 48731
w = 357
y
应该是 7355
。
最佳答案
pow
不会自动计算 modular multiplicative inverse为你。相反,我们可以自己计算它(比如通过扩展欧里德算法),然后将 pow(a,-b,c)
重写为 pow((a^-1) mod c, b , c)
。从 this question 窃取 MMI 代码:
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
我们得到
>>> g = 11444
>>> p = 48731
>>> w = 357
>>> modinv(g, p)
29420
>>> pow(modinv(g, p), w, p)
7355
关于python - 模块化 pow() 中的负幂,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34119110/