在Python模反元素功能

问题描述：

有没有一些标准的Python模块包含一个函数来计算一个数值模反元素，即一批 Y = invmod（X，P），使得 X * Y == 1（模p）？谷歌似乎并没有给这个有什么好的提示。

Does some standard Python module contain a function to compute modular multiplicative inverse of a number, i.e. a number y = invmod(x, p) such that x*y == 1 (mod p)? Google doesn't seem to give any good hints on this.

当然，人们可以拿出自酿10内胆扩展欧几里德算法，但为什么重塑轮。

Of course, one can come up with home-brewed 10-liner of extended Euclidean algorithm, but why reinvent the wheel.

例如，Java的的BigInteger 的 modInverse 方法。不Python中有相似的地方？

For example, Java's BigInteger has modInverse method. Doesn't Python have something similar?

答

也许有人会觉得有帮助（从wikibooks):

Maybe someone will find this useful (from 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

在Python模反元素功能

相关推荐