Modular multiplicative inverse function in Python Modular multiplicative inverse function in Python python python

Modular multiplicative inverse function in Python


Python 3.8+

y = pow(x, -1, p)

Python 3.7 and earlier

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


If your modulus is prime (you call it p) then you may simply compute:

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

Or in Python proper:

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

Here is an example done at the prompt:

m = 1000000007x = 1234567y = pow(x,m-2,m)y989145189Lx*y1221166008548163Lx*y % m1L


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:

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

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

Disclaimer: I'm the current maintainer of the gmpy library.

Updated answer 2

gmpy2 now properly raises an exception when the inverse does not exists:

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