Python中的模块化乘法反函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4798654/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Modular multiplicative inverse function in Python
提问by dorserg
Does some standard Python module contain a function to compute modular multiplicative inverseof 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.
难道一些标准的Python模块包含一个函数来计算模反元素一个号码，即一些y = invmod(x, p)这样x*y == 1 (mod p)？谷歌似乎没有对此给出任何好的提示。
Of course, one can come up with home-brewed 10-liner of extended Euclidean algorithm, but why reinvent the wheel.
当然，可以想出自制的 10-liner扩展欧几里得算法，但为什么要重新发明轮子。
For example, Java's BigIntegerhas modInversemethod. Doesn't Python have something similar?
例如，Java 的BigIntegerhasmodInverse方法。Python 没有类似的东西吗？
回答by phkahler
If your modulus is prime (you call it p) then you may simply compute:
如果您的模数是素数（您称之为p），那么您可以简单地计算：
y = x**(p-2) mod p # Pseudocode
Or in Python proper:
或者在 Python 中：
y = pow(x, p-2, p)
Here is someone who has implemented some number theory capabilities in Python: http://www.math.umbc.edu/~campbell/Computers/Python/numbthy.html
这是在 Python 中实现了一些数论功能的人：http: //www.math.umbc.edu/~campbell/Computers/Python/numbthy.html
Here is an example done at the prompt:
这是在提示符下完成的示例：
m = 1000000007
x = 1234567
y = pow(x,m-2,m)
y
989145189L
x*y
1221166008548163L
x*y % m
1L
回答by casevh
You might also want to look at the gmpymodule. It is an interface between Python and the GMP multiple-precision library. gmpy provides an invert function that does exactly what you need:
您可能还想查看gmpy模块。它是 Python 和 GMP 多精度库之间的接口。gmpy 提供了一个可以完全满足您需要的反转函数：
>>> import gmpy
>>> gmpy.invert(1234567, 1000000007)
mpz(989145189)
Updated answer
更新答案
As noted by @hyh , the gmpy.invert()returns 0 if the inverse does not exist. That matches the behavior of GMP's mpz_invert()function. gmpy.divm(a, b, m)provides a general solution to a=bx (mod m).
正如@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()will return a solution when gcd(b,m) == 1and raises an exception when the multiplicative inverse does not exist.
divm()将gcd(b,m) == 1在乘法逆不存在时返回解决方案并引发异常。
Disclaimer: I'm the current maintainer of the gmpy library.
免责声明：我是 gmpy 库的当前维护者。
Updated answer 2
更新了答案 2
gmpy2 now properly raises an exception when the inverse does not exists:
当逆不存在时，gmpy2 现在正确地引发异常：
>>> import gmpy2
>>> gmpy2.invert(0,5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: invert() no inverse exists
回答by David Sulpy
To figure out the modular multiplicative inverse I recommend using the Extended Euclidean Algorithm like this:
要找出模乘逆，我建议使用扩展欧几里得算法，如下所示：
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
回答by M?rt Bakhoff
Maybe someone will find this useful (from wikibooks):
也许有人会发现这很有用（来自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
回答by Eric
Here is my code, it might be sloppy but it seems to work for me anyway.
这是我的代码，它可能很草率，但无论如何它似乎对我有用。
# 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
回答by HKTonyLee
Here is a one-liner for CodeFights; it is one of the shortest solutions:
这是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]
It will return -1if Ahas no multiplicative inverse in n.
-1如果A中没有乘法逆，它将返回n。
Usage:
用法：
MMI(23, 99) # returns 56
MMI(18, 24) # return -1
The solution uses the Extended Euclidean Algorithm.
该解决方案使用扩展欧几里得算法。
回答by OutputLogic
Many of the links above are broken as for 1/23/2017. I found this implementation: https://courses.csail.mit.edu/6.857/2016/files/ffield.py
至 2017 年 1 月 23 日，上面的许多链接都已断开。我找到了这个实现：https: //courses.csail.mit.edu/6.857/2016/files/ffield.py
回答by Mohd Shibli
Well, I don't have a function in python but I have a function in C which you can easily convert to python, in the below c function extended euclidian algorithm is used to calculate inverse mod.
好吧，我在 python 中没有函数，但我在 C 中有一个函数，您可以轻松地将其转换为 python，在下面的 c 函数中，扩展欧几里得算法用于计算逆模。
int imod(int a,int n){
int c,i=1;
while(1){
c = n * i + 1;
if(c%a==0){
c = c/a;
break;
}
i++;
}
return c;}
Python Function
Python 函数
def imod(a,n):
i=1
while True:
c = n * i + 1;
if(c%a==0):
c = c/a
break;
i = i+1
return c
Reference to the above C function is taken from the following link C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers
上面C函数的参考取自以下链接C程序，求两个相对质数的模乘逆
回答by BvdM
The code above will not run in python3 and is less efficient compared to the GCD variants. However, this code is very transparent. It triggered me to create a more compact version:
上面的代码不会在 python3 中运行，并且与 GCD 变体相比效率较低。但是，这段代码非常透明。它促使我创建一个更紧凑的版本：
def imod(a, n):
c = 1
while (c % a > 0):
c += n
return c // a
回答by Chris Chudzicki
Sympy, a python module for symbolic mathematics, has a built-in modular inverse function if you don't want to implement your own (or if you're using Sympy already):
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'
This doesn't seem to be documented on the Sympy website, but here's the docstring: Sympy mod_inverse docstring on Github
这似乎没有记录在 Sympy 网站上，但这是文档字符串：Github 上的 Sympy mod_inverse 文档字符串
