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`

.

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`

.

`pow()`

Builtin FunctionWe 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 `