模块化幂函数中的负幂

Question

如何在模运算中使用具有负指数的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 "<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。

- kAldown

---

抱歉，什么？你有一个实际的问题吗？最好提供一个 [mcve]，这样我们才能为你提供答案。 - Martijn Pieters

pow(10, -2) 会产生 0.01，所以你说 Python 不能使用负数 至少是你的一个误解。 - Martijn Pieters

我认为他的意思是，对于非常小的数字缺乏精度会产生0.0。 - Pallav Agarwal

我认为OP真正想知道的是“Python是否会自动计算模反元素以支持负模幂？” 答案是否定的。 g^-1 mod p等于29420，而pow(29420, 357, 48731) == 7355；你需要自己计算29420（例如使用扩展欧几里得算法）。 - DSM

@DSM：在OP的编辑后，我已经重新开放了这个问题，但是你的解释更好。也许你可以将它编辑进问题中。 - Martijn Pieters

Answer 1

从 Python 3.8 开始，你可以这样做。Python 3.9 添加了关键字参数。查看这里的代码。它们的用法是：

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

- A_Arnold

Answer 2

pow不会自动计算模乘逆元，我们需要自己计算（可以通过扩展欧几里得算法），然后将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

- DSM

---

在p为质数的情况下（就像这里一样），计算modinv(a, p)的更简单的实现方式是pow(a, p-2, p)。 - interjay

Python3.8的新特性：pow现在可以计算模反元素。https://docs.python.org/3/library/functions.html#pow - Stef