A python code for calculate GCD and modular multiplicative inverse

modular-multiplicative-inverse.py

def inverseMod(a, m):
    for i in range(1,m):
        if ( m*i + 1) % a == 0:
            return ( m*i + 1) // a
    return None

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.
    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a


a = input("Input a number of \"a\": ")
b = input("Input a number of \"b\": ")


print("The Greatest Common Divisor of %s and %s is %s" % (a, b, gcd(a,b)))
print("The Modular inverses of %s modulo %s is %s" % (a, b, inverseMod(a,b)))

def inverseMod(a, m):
for i in range(1,m):
if ( mi + 1) % a == 0:
return ( mi + 1) // a
return None

The complexity of above code snippet is O(m) in worst case.
So it is not suitable to use this method for larger numbers like million or trillion.

You can try this

a=int(input("Enter number : "))
b=int(input("Enter mod : "))

r1=b;r2=a
if(r1<r2):
(r1,r2)=(r2,r1)
t1=0;t2=1

while(r1>1):
r=r1%r2
q=r1//r2
r1=r2
r2=r
t=t1-(q*t2)
t1=t2
t2=t

if(r1!=1):
print("Invers of ",a," in mod ",b," does not exist.")
else:
print("Invers of ",a," in mod ",b," is",t1,".")

Complexity is reduced to O(Lom(m)).

Note that in Python 3.8 onward there's a three argument form of pow that allows calculating the modular inverse simply as pow(a, -1, m). Notably this is efficiently implemented, e.g. pow(10**30, -1, 2**255-19) completes in 5 microseconds.

See: https://docs.python.org/3/library/functions.html#pow