Solving a modular equation (Python)

Question

I have what seems to be an easy problem to solve in Python, but as I am new to python I am unaware on how to solve this.

All I am trying to solve is...

(x * e) mod k = 1 (where e and k are known values)

Is there any simple way of doing this?

Answer 1

Searching for x is basically looking for inverse element of e mod k which can be done by Extended Euclidean Algorithm which nicely implemented and used for modular inverse here:

# Iterative Algorithm (xgcd)
def iterative_egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a,b%a; m,n = x-u*q,y-v*q # use x//y for floor "floor division"
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

def modinv(a, m):
    g, x, y = iterative_egcd(a, m) 
    if g != 1:
        return None
    else:
        return x % m

_{Note: I don't own the code}

And usage:

>>> e = 3
>>> k = 7
>>> x = modinv(e,k)
>>> x
5
>>> e*x % k
1

Answer 2

If you would prefer to use the popular math library gmpy instead of coding your own algorithm, then the function to solve your equation (i.e., finding the modular inverse) is called invert(). After installing the current version of gmpy (version 2 as of this writing), you would simply do this:

>>> import gmpy2
>>> x = gmpy2.invert(e, k) # (Supply e and k here)

Note: gmpy will return the value in its native mpz (multi-precision integer) format, however you can treat the value just like a regular int in Python code without problem, or if you prefer, cast it to an int explicitly:

>>> x = int(gmpy2.invert(3, 7))

Here is the documentation for gmpy2.invert():

invert(x, m) -> mpz

Return y such that x*y == 1 (mod m). Raises ZeroDivisionError if no inverse exists.

The advantage to this approach is that the gmpy algorithm is fast and you don't need to type any extra code. The disadvantage is you have to import a third-party module.

Answer 3

Since Python 3.8, the simple way is now:

pow(e, -1, k) # x is the output of this statement

Example:

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