Calculate Modular Multiplicative Inverse in Python

  1. Modular Multiplicative Inverse Using the Naive Iterative Approach
  2. Modular Multiplicative Inverse Using pow() Builtin Function

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 and 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
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Python Math

  • Square Root in Python
  • Calculate the Inverse Tangent in Python