Modular Mulitplicative Inverse

source geeksforgeeks

Input:  a = 3, m = 11
Output: 4
3.x mod 11 = 1
3.4 mod 11 = 1

4 < 11

Method

1. Naive Method, O(m)
2. Extended Euler’s GCD algorithm, O(Log m) [Works when a and m are coprime]
3. Fermat’s Little theorem, O(Log m) [Works when ‘m’ is prime]

Method 1

Time Complexity: O(m)

def modInverse(a, m):

    for x in range(1, m):
        if (((a%m) * (x%m)) % m == 1):
            return x
    return -1

a = 3
m = 11

print(modInverse(a, m))

Method 2

(Works when m and a are coprime)

Time Complexity: O(Log m)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1

	if (m == 1):
		return 0

	while (a > 1):

		# q is quotient
		q = a // m

		t = m

		# m is remainder now, process
		# same as Euclid's algo
		m = a % m
		a = t
		t = y

		# Update x and y
		y = x - q * y
		x = t

	# Make x positive
	if (x < 0):
		x = x + m0

	return x

a = 3
m = 11

print("Modular multiplicative inverse is", modInverse(a, m))

Bentuk sederhana

def modInv(a, m, x1, y1):
	if a <= 1:
		if y1 < 0:
			y1 += x1
		return y1
	x=y1-(a//m)*x1
	y=x1
	return modInv(m, a%m, x, y)
a, m = 13, 107
x, y = 0, 1
print(modInv(a, m, x, y))

Method 3

(Works when m is prime)

Time Complexity: O(Log m)

def modInverse(a, m):

    g = gcd(a, m)

    if (g != 1):
        print("Inverse doesn't exist")

    else:

        # If a and m are relatively prime,
        # then modulo inverse is a^(m-2) mode m
        print("Modular multiplicative inverse is ",
              power(a, m - 2, m))

# To compute x^y under modulo m


def power(x, y, m):

    if (y == 0):
        return 1

    p = power(x, y // 2, m) % m
    p = (p * p) % m

    if(y % 2 == 0):
        return p
    else:
        return ((x * p) % m)

# Function to return gcd of a and b


def gcd(a, b):
    if (a == 0):
        return b

    return gcd(b % a, a)


# Driver Code
a = 3
m = 11

# Function call
modInverse(a, m)

Bentuk sederhana

a = 3
m = 11
print(pow(a, m-2, m)) 		#  	a**(m-2) % m