Python 中的模块化乘法反函数

如果你的模是质数(你称之为 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

您可能还想查看 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()会返回一个解决方案并引发一个异常。

免责声明: 我是 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

为了找出模反元素，我推荐使用这样的扩展欧几里得算法:

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

Python 3.8 +

y = pow(x, -1, p)

Python 3.7及更早版本

也许有人会发现这很有用(来自 维基百科) :

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

这是我的代码，它可能是草率的，但它似乎为我工作无论如何。

# 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

下面是 代码战的一行程序，它是最短的解决方案之一:

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]

如果 A在 n中没有倒数，它将返回 -1。

用法:

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

解决方案使用 扩展欧几里得算法。

我在 python 中没有函数，但是我在 C 中有一个函数，你可以很容易地将它转换成 python，在下面的 c 函数中，扩展的欧几里得算法被用来计算逆 mod。

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 函数

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

对上述 C 函数的引用来自以下链接 程序找出两个相对素数的模反元素

上面的代码不会在 python3中运行，并且与 GCD 变体相比效率较低。但是，这段代码是非常透明的。这促使我创建了一个更紧凑的版本:

def imod(a, n):
c = 1
while (c % a > 0):
c += n
return c // a

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 网站上似乎没有这方面的文档，但是这里有一个 docstring: Github 上的 sympymod _ verse 文档字符串

我尝试了不同的解决方案，最后我使用了这个方案:

def egcd(a, b):
lastremainder, remainder = abs(a), abs(b)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if a < 0 else 1), lasty * (-1 if b < 0 else 1)




def modinv(a, m):
g, x, y = self.egcd(a, m)
if g != 1:
raise ValueError('modinv for {} does not exist'.format(a))
return x % m

Python 中的模反转

下面是一个简洁的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，简化后只返回单利率系数。

从 cpython 实现 源代码:

def invmod(a, n):
b, c = 1, 0
while n:
q, r = divmod(a, n)
a, b, c, n = n, c, b - q*c, r
# at this point a is the gcd of the original inputs
if a == 1:
return b
raise ValueError("Not invertible")

根据上面的代码注释，它可以返回小的负值，所以您可以在返回 b 之前检查是否为负，并在负值时添加 n。

在3.8 Python 中，pow ()函数可以取一个模和一个负整数。参见 给你。他们的情况是如何使用它

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