我们如何pow
在模块化环境中使用负指数?
pow(x,y,[z])如果存在z,则x和y必须为整数类型,并且y必须为非负数。
>>> pow(11444, -357) 0.0 >>> pow(11444, -357) % 48731 0.0 >>> pow(11444, -357, 48731) Traceback (most recent call last): File "", line 1, in 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
不会自动为您计算模块化的乘法逆。相反,我们可以自己计算(例如通过扩展的Eulidean算法),然后重写pow(a,-b,c)
为pow((a^-1) mod c, b, c)
。从这个问题窃取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