Python中的模块化乘法逆函数

Question

一些标准的Python模块是否包含一个函数来计算一个数字的模乘法逆,即一个y = invmod(x, p)这样的数字x*y == 1 (mod p)？谷歌似乎没有给出任何好的提示.

当然,人们可以提出自制的10线延伸欧几里德算法,但为什么要重新发明轮子.

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

Answer 1

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

您可能还想查看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 4

从 3.8 开始，pythons pow() 函数可以采用模数和负整数。见这里。他们如何使用它的案例是

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

Answer 5

这是CodeFights的单线程 ; 它是最短的解决方案之一:

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]

-1如果A没有乘法逆,它将返回n.

用法:

MMI(23, 99) # returns 56
MMI(18, 24) # return -1

该解决方案使用扩展欧几里德算法.

Answer 6

Sympy，为象征性的数学Python模块，具有内置式模块反函数，如果你不希望实现自己的（或者，如果您已经在使用Sympy）：

from sympy import mod_inverse

mod_inverse(11, 35) # returns 16
mod_inverse(15, 35) # raises ValueError: 'inverse of 15 (mod 35) does not exist'

这似乎没有在Sympy网站上记录，但这里是文档字符串：Github上的Sympy mod_inverse文档字符串

Answer 7

这是一个简洁的 1-liner 代码，无需使用任何外部库即可完成此操作。

# Given 0<a<b, returns the unique c such that 0<c<b and a*c == gcd(a,b) (mod b).
# In particular, if a,b are relatively prime, returns the inverse of a modulo b.
def invmod(a,b): return 0 if a==0 else 1 if b%a==0 else b - invmod(b%a,a)*b//a

请注意，这实际上只是 egcd，经过简化以仅返回感兴趣的单个系数。