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