Python中的模块乘法逆函数
一些标准的Python模块是否包含一个函数来计算一个数的模乘法逆 ，即一个数y = invmod(x, p) ，使得x*y == 1 (mod p) ？ 谷歌似乎没有给出任何好的提示。
当然，我们可以拿出自制的10线扩展欧几里德algorithm ，但为什么要重新发明轮子。
例如，Java的BigInteger有modInverse方法。 Python没有类似的东西吗？
也许有人会觉得这有用（从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
如果你的模数是素数（你称之为p ），那么你可以简单地计算：
y = x**(p-2) mod p # Pseudocode
或者正确的Python：
y = pow(x, p-2, p)
这里是一些在Python中实现了一些数字理论function的人： http : //userpages.umbc.edu/~rcampbel/Computers/Python/numbthy.html
以下是在提示符下完成的示例：
m = 1000000007 x = 1234567 y = pow（x，m-2，m） ÿ 989145189L X * Y 1221166008548163L x * y％m 1L
你可能也想看看gmpy模块。 它是Python和GMP多精度库之间的接口。 gmpy提供了一个反转function，完全符合你的需求：
>>> import gmpy >>> gmpy.invert(1234567, 1000000007) mpz(989145189)
更新了答案
正如@hyh指出的那样，如果反函数不存在， gmpy.invert()将返回0。 这符合GMP的mpz_invert()函数的行为。 gmpy.divm(a, b, m)为a=bx (mod m)提供了一个通用的解决scheme。
>>> 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)
当gcd(b,m) == 1时， divm()将返回一个解gcd(b,m) == 1并且当乘法inverse不存在时引发一个exception。
免责声明：我是gmpy库的当前维护者。
更新了答案2
现在gmpy2在反转不存在时正确地引发exception：
>>> import gmpy2 >>> gmpy2.invert(0,5) Traceback (most recent call last): File "<stdin>", line 1, in <module> ZeroDivisionError: invert() no inverse exists
这里是CodeFights的单线程 ; 这是最短的解决scheme之一：
MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, sA//n*t, N or n),-1)[n<1]
如果A在n没有乘法倒数，它将返回-1 。
用法：
MMI(23, 99) # returns 56 MMI(18, 24) # return -1
该解决scheme使用扩展欧几里德algorithm 。
这里是我的代码，它可能是马虎，但似乎无论如何对我工作。
# a is the number you want the inverse for # b is the modulus def mod_inverse(a, b): r = -1 B = b A = a eq_set = [] full_set = [] mod_set = [] #euclid's algorithm while r!=1 and r!=0: r = b%a q = b//a eq_set = [r, b, a, q*-1] b = a a = r full_set.append(eq_set) for i in range(0, 4): mod_set.append(full_set[-1][i]) mod_set.insert(2, 1) counter = 0 #extended euclid's algorithm for i in range(1, len(full_set)): if counter%2 == 0: mod_set[2] = full_set[-1*(i+1)][3]*mod_set[4]+mod_set[2] mod_set[3] = full_set[-1*(i+1)][1] elif counter%2 != 0: mod_set[4] = full_set[-1*(i+1)][3]*mod_set[2]+mod_set[4] mod_set[1] = full_set[-1*(i+1)][1] counter += 1 if mod_set[3] == B: return mod_set[2]%B return mod_set[4]%B
为了找出模乘法逆，我推荐使用这样的扩展欧几里德algorithm：
def multiplicative_inverse(a, b): origA = a X = 0 prevX = 1 Y = 1 prevY = 0 while b != 0: temp = b quotient = a/b b = a%b a = temp temp = X a = prevX - quotient * X prevX = temp temp = Y Y = prevY - quotient * Y prevY = temp return origA + prevY
上面的许多链接是截至2017年1月23日。 我发现这个实现： https ： //courses.csail.mit.edu/6.857/2016/files/ffield.py
