JIYIK CN >

If we have two numbers aand m, then athe modular multiplicative inverse of is mmodulo xif:

a * x % m = 1

In this case, the multiplicative inverse exists only if aand mare relatively prime, that is, if the greatest common divisor of aand mis 1.

xThe value of can range from 1to m-1.

Modular multiplicative inverse using naive iterative method

Suppose we need to mfind athe multiplicative inverse of modulo . If a modular multiplicative inverse exists, its value can be from 1to m-1. Therefore, we iterate over this range and check the condition for modular multiplicative inverse. If any number in the range satisfies the condition, we take the number as modular 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 find_mod_invfunction called that takes aand mas input and returns the multiplicative inverse of mmodulo .a

If number does not have a multiplicative reciprocal modulo , it will raise a asum .maException

From the above example, we can see that the modular multiplicative inverse of 22under module is .1317

pow()Modular inverse using built-in functions

We can also use Python's built-in function pow()to calculate 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

pow()To compute a modular multiplicative inverse using the method, pow()the first argument to the method will be the number whose modular inverse you want to find, the second argument will be the modulus to subtract 2, and the last argument will be the order of the moduli.

However, for Python 3.8versions and later, we can replace the second parameter 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