Modular multiplicative inverse in Python

In this tutorial, we will learn how to find modular multiplicative inverse using Python. Let’s try to understand what this term means.

Modular Multiplicative Inverse: Consider two integers n and m. MMI(Modular Multiplicative Inverse) is an integer(x), which satisfies the condition (n*x)%m=1. x lies in the domain {0,1,2,3,4,5,…..,m-1}.

naive: Modular multiplicative inverse in Python

This is the easiest way to get the desired output. Let’s understand this approach using a code.

def mod_Inv(x,y):
    for i in range(y):
        if (x*i)%y==1:
            return i
print("MMI is ",mod_Inv(3,11))

we have created a simple function mod_Inv(x,y) which takes two arguments and returns MMI.

Output:
MMI is  4

This method is easy but it fails to perform fast. Its time complexity is O(m).

By Fermat’s little theorem: Modular multiplicative inverse

This theorem solves the problem of time. Let’s consider a condition that we have two numbers ‘a’ and ‘m’ where ‘m’ is prime.
 am-1   ≡  1  (mod m) this statement means that if ‘ m’ is prime MMI can be calculated as using the relation. Now if we multiply the equation by a-1  we get the following equation  a-1≡ a m-2(mod m).

 

Let’s understand this by the implementation of a program.

def cal_gcd(a, b) : 
    if (a == 0) : 
        return b 
         
    return cal_gcd(b % a, a)

we have calculated GCD to get the common divisor.

def cal_power(x, y, m) : 
      
    if (y == 0) : 
    	
    	return 1

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

we use function cal_power(x,y,m), to satisfy Fermat’s condition and return the modular inverse.

def mod_Inv(a, m) : 
      
    gcd = cal_gcd(a, m) 
      
    if (gcd != 1) : 
        print("Inverse doesn't exist") 
    else : 
    	print("Modular multiplicative inverse is ", cal_power(a, m - 2, m))

this function is the sub-driving function.  Here we check if the gcd is 1 or not. If 1, it suggests that m isn’t prime. So, in this case, the inverse doesn’t exist.

a = 3; m = 11
mod_Inv(a,m) 
output:
Modular multiplicative inverse is  4

This is how we can calculate modular multiplicative inverse using Fermat’s little theorem. The reason we have used this method is the time factor. The time complexity of Fermat’s little theorem is O(log m).

Also read:

Leave a Reply

Your email address will not be published. Required fields are marked *