python - Python中的模乘反函数

Question

某些标准 Python 模块是否包含计算函数 modular multiplicative inverse一个数字，即一个数字 y = invmod(x, p) 使得 x*y == 1 (mod p)?谷歌似乎没有给出任何好的提示。

当然，可以想出 extended Euclidean algorithm 的自制 10-liner ，但为什么要重新发明轮子。

例如，Java 的 BigInteger 有 modInverse 方法。 Python没有类似的东西吗？

Answer 1

Python 3.8+

y = pow(x, -1, p)

Python 3.7 及更早版本

也许有人会觉得这很有用(来自 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