Modular Multiplicative Inverse Function in Python

Question

Does the standard Python module have a function for computing the modular multiplicative inverse , that is, the number y = invmod(x, p) , such that x*y == 1 (mod p) ? Google doesn't seem to give any good advice on this.

Of course, you can come up with a 10-liner with internal support for the advanced Euclidean algorithm , but why reinvent the wheel.

For example, Java BigInteger has a modInverse method. Does Python have something like this?

Answer 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 

Answer 2

If your module is simple (you call it p ), then you can simply calculate:

 y = x**(p-2) mod p # Pseudocode 

Or in Python itself:

 y = pow(x, p-2, p) 

Here is someone who has implemented some of the possibilities of number theory in Python: http://www.math.umbc.edu/~campbell/Computers/Python/numbthy.html

Here is an example made at the invitation:

 m = 1000000007 x = 1234567 y = pow(x,m-2,m) y 989145189L x*y 1221166008548163L x*y % m 1L 

Answer 3

You can also look at the gmpy module. This is the interface between Python and the GMP multiple-precision library. gmpy provides an invert function that does exactly what you need:

 >>> import gmpy >>> gmpy.invert(1234567, 1000000007) mpz(989145189) 

Updated Answer

As @hyh notes, gmpy.invert() returns 0 if the opposite does not exist. This is consistent with GMP mpz_invert() behavior. gmpy.divm(a, b, m) provides a general solution for 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 the solution when gcd(b,m) == 1 and throw an exception when the multiplicative inverse does not exist.

Disclaimer: I am the current custodian of the gmpy library.

Updated Answer 2

gmpy2 now correctly throws an exception when the converse does not exist:

 >>> import gmpy2 >>> gmpy2.invert(0,5) Traceback (most recent call last): File "<stdin>", line 1, in <module> ZeroDivisionError: invert() no inverse exists 

Answer 4

Here is a single line for CodeFights ; this 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, sA//n*t, N or n),-1)[n<1] 

It will return -1 if A does not have the multiplicative inverse of n .

Using:

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

The solution uses the Extended Euclidean Algorithm .

Answer 5

Sympy , the Python module for symbolic mathematics, has a built-in modular inverse function if you do not want to implement your own (or if you are already using 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 site, but here is the documentation line : Sympy mod_inverse the documentation line on Github

Answer 6

Here is my code, it may be messy, but it seems to work for me.

 # 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 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 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 

Answer 7

The above code will not work in python3 and is less efficient compared to GCD variants. However, this code is very transparent. This prompted me to create a more compact version:

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

Answer 8

To calculate the modular multiplicative inverse, I recommend using the Extended Euclidean Algorithm as follows:

 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 

Answer 9

I try different solutions from this topic, and in the end I use this:

 def egcd(self, 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(self, a, m): g, x, y = self.egcd(a, m) if g != 1: raise ValueError('modinv for {} does not exist'.format(a)) return x % m 

Modular_inverse in Python

Answer 10

Well, I do not have a function in Python, but I have a function in C that you can easily convert to Python, in the algorithm of the function c below the extended Euclidean is used to calculate the inverse mode.

 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

 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 

A link to the aforementioned function C is taken from the following program C to find the modular multiplicative inversion of two relatively prime numbers

Answer 11

Here is a brief 1-liner that does this, without using any external libraries.

 # 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 

Note that this is really just egcd, optimized to return only one coefficient of interest.

Answer 12

from the Cpython implementation of the source code :

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

according to the comment on this code, it can return small negative values, so you can check if it is negative, and add n if it is negative before returning b.

Answer 13

Many of the links above are broken as of 1/23/2017. I found this implementation: https://courses.csail.mit.edu/6.857/2016/files/ffield.py