Python中的模乘反函数

Question

一些标准的Python模块是否包含一个函数来计算一个数的modular multiplicative inverse，即一个数y = invmod(x, p)，从而x*y == 1 (mod p)？谷歌似乎对此没有给出任何好的暗示。

当然，一个人可以想出家酿10行extended Euclidean algorithm，但为什么要重新发明轮子。

例如，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

也许有人会觉得这很有用（从wikibooks）：

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

Answer 3

如果你的模是素数（你称它为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