Python中的模块化乘法逆函数。

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.

是否有一些标准的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班轮扩展欧几里得算法，但为什么要重新发明*。

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

例如，Java的BigInteger具有modInverse方法。Python没有类似的东西吗?

10 个解决方案

#1

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

#2

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://userpages.umbc.edu/~rcampbel/Computers/Python/numbthy.html

这里有一个人在Python中实现了一些数论功能:http://userpages.umbc.edu/~rcampbel/ computer /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

#3

You might also want to look at the gmpy module. 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) == 1 and raises an exception when the multiplicative inverse does not exist.

当gcd(b,m) == 1时，divm()将返回一个解决方案，当乘法逆不存在时抛出异常。

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

#4

Here is a one-liner for CodeFights; it is one of the shortest solutions:

这里有一段代码冲突的代码;它是最短的解之一:

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 -1 if A has no multiplicative inverse in n.

如果A在n中没有乘法逆，它会返回-1。

Usage:

用法:

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

The solution uses the Extended Euclidean Algorithm.

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

#5

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

#6

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

#7

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。

#8

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函数中扩展了euclidian算法来计算逆模。

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程序中找到两个相对素数的模乘法逆。

#9

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

#10

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):

作为符号数学的python模块，如果您不想实现自己的(或者您已经使用了很好)，那么它有一个内置的模块逆函数:

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

这似乎并没有在“症状”网站上记录下来，但这里有一个docstring: Github上的“健壮的mod_逆docstring”。