Modular multiplicative inverse function in Python

Question

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 = 1000000007
x = 1234567
y = pow(x,m-2,m)
y
989145189L
x*y
1221166008548163L
x*y % m
1L

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

As of 3.8 pythons pow() function can take a modulus and a negative integer. See here. Their case for how to use it is

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