# Python - How To Calculate Modular Multiplicative Inverse in Python

ID : 345

viewed : 92

Tags : PythonPython Math  95

If we have two numbers `a` and `m`, then the modular multiplicative inverse of `a` is `x` under modulo `m` if:

``a * x % m = 1 ``

In this case, the multiplicative inverse exists only if `a` and `m` are relatively prime i.e. if the greatest common divisor of both `a` and `m` is `1`.

The value of `x` can range from `1` to `m-1`.

## Modular Multiplicative Inverse Using the Naive Iterative Approach

Suppose we need to find the multiplicative inverse of `a` under modulo `m`. If the modulo multiplicative inverse exists, its value can range from `1` to `m-1`., Hence, we iterate through this range and check the condition for modulo multiplicative inverse. If any number within the range satisfies the condition, we have the number as modulo multiplicative inverse.

``def find_mod_inv(a,m):      for x in range(1,m):         if((a%m)*(x%m) % m==1):             return x     raise Exception('The modular inverse does not exist.')   a = 13 m = 22  try:     res=find_mod_inv(a,m)     print("The required modular inverse is: "+ str(res))  except:     print('The modular inverse does not exist.') ``

Output:

``The required modular inverse is: 17 ``

Here, we have a function named `find_mod_inv` which takes `a` and `m` as input and returns the multiplicative inverse of `a` under modulo `m`.

If the number `a` does not have a multiplicative inverse of `a` under modulo `m`, it will raise an exception.

From the example above, we can see the modular multiplicative inverse of `13` under modulo `22` is `17`.

## Modular Multiplicative Inverse Using `pow()` Builtin Function

We can also use the built-in function `pow()` from Python to compute the modular multiplicative inverse of a number.

``a=38 m=97 res = pow(a, m-2, m) print("The required modular inverse is: "+ str(res)) ``

Output:

``The required modular inverse is: 23 ``

To calculate the modulo multiplicative inverse using the `pow()` method, the first parameter to the `pow()` method will be the number whose modulo inverse is to be found, the second parameter will be the order of modulo subtracted by 2 and the last parameter will be the order of modulo.

However, for `Python 3.8` and above, we can replace the second argument with `-1`.

``a=38 m=97 res = pow(a, -1, m) print("The required modular inverse is: "+ str(res)) ``

output:

``The required modular inverse is: 23 ``