模块化 pow() 中的负幂

Question

我们如何在模块化上下文中使用 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.

Answer 1

pow 不会自动计算 modular multiplicative inverse for you. Instead, we can compute it ourselves (say via the extended Eulidean algorithm) and then rewrite pow(a,-b,c) as pow((a^-1) mod c, b, c). Stealing the MMI code from this question:

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

Answer 2

从 python 3.8 开始，您可以执行此操作。 3.9 添加关键字参数。查看那里的代码 here。用法是

>>> pow(38, -1, mod=97)
23
>>> 23 * 38 % 97 == 1
True

模块化 pow() 中的负幂

Negative power in modular pow()

python

math

modulo

pow