Calculate Modular Multiplicative Inverse in Python
 Modular Multiplicative Inverse Using the Naive Iterative Approach

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 m1
.
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 m1
., 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 builtin function pow()
from Python to compute the modular multiplicative inverse of a number.
a=38
m=97
res = pow(a, m2, 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