Python中的模乘逆函数

Question

有没有哪个标准的Python模块里包含一个可以计算数字的模乘逆的函数，也就是说，找一个数字 y = invmod(x, p)，使得 x*y == 1 (mod p)？在谷歌上似乎找不到什么好的线索。

当然，自己写个十行代码实现扩展欧几里得算法是可以的，但为什么要重复造轮子呢。

比如，Java的 BigInteger 有一个 modInverse 方法。那Python有没有类似的东西呢？

Answer 1

你可能还想看看 gmpy 这个模块。它是Python和GMP多精度库之间的一个接口。gmpy提供了一个反转函数，正好满足你的需求：

>>> import gmpy
>>> gmpy.invert(1234567, 1000000007)
mpz(989145189)

更新的回答

正如@hyh提到的，gmpy.invert() 如果反转不存在，会返回0。这和GMP的 mpz_invert() 函数的表现是一致的。gmpy.divm(a, b, m) 提供了一个通用的解决方案来处理 a=bx (mod m)。

>>> gmpy.divm(1, 1234567, 1000000007)
mpz(989145189)
>>> gmpy.divm(1, 0, 5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 8)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 9)
mpz(7)

divm() 在 gcd(b,m) == 1 的情况下会返回一个解，如果乘法逆元不存在，则会抛出一个异常。

免责声明：我是gmpy库的当前维护者。

更新的回答 2

gmpy2现在在逆元不存在时会正确抛出异常：

>>> import gmpy2

>>> gmpy2.invert(0,5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: invert() no inverse exists

Answer 2

如果你的模数是一个质数（我们称它为 p），那么你可以简单地计算：

y = x**(p-2) mod p  # Pseudocode

或者用标准的Python代码：

y = pow(x, p-2, p)

这里有一个人已经在Python中实现了一些数论的功能：http://www.math.umbc.edu/~campbell/Computers/Python/numbthy.html

下面是一个在命令行中完成的例子：

m = 1000000007
x = 1234567
y = pow(x,m-2,m)
y
989145189L
x*y
1221166008548163L
x*y % m
1L

Answer 3

Python 3.8及以上版本

y = pow(x, -1, p)

Python 3.7及之前版本

也许有人会觉得这个有用（来自 维基教科书）：

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