Python Program for Modular Multiplicative Inverse

Python / By

In the previous article, we have discussed Python Program to Find Square Root Under Modulo k (When k is in Form of 4*i + 3)

Given two integers and the task is to find the modular multiplicative inverse of ‘first number’ under modulo ‘second number’.

The modular multiplicative inverse is an integer ‘x’ such that

first number x ≡ 1 (mod second number)

The value of x should be in the range 0 to 1, 2,…second number-1, i.e. in the integer modulo second number ring.

If and only if the first number and second number are relatively prime (i.e., if gcd( first number, second number) = 1), the multiplicative inverse of “first number modulo second number” exists.

Examples:

Example1:

Input:

Given First Number = 10
Given Second Number = 17

Output:

The modular multiplicative inverse of given first number under modulo second number =  12

Example2:

Input:

Given First Number = 4
Given Second Number = 9

Output:

The modular multiplicative inverse of given first number under modulo second number =  7

Program for Modular Multiplicative Inverse in Python

Below are the ways to find the modular multiplicative inverse of ‘first number’ under modulo ‘second number’ in python.

Method #1: Using For Loop (Static Input)

Approach:

  • Give the first number as static input and store it in a variable.
  • Give the second number as static input and store it in another variable.
  • Pass the given first and second numbers as the arguments to the modular_MultInverse function.
  • Create a function to say modular_MultInverse which takes the given first and second numbers as the arguments and returns the modular multiplicative inverse of ‘first number’ under modulo ‘second number’.
  • Calculate the value of the given first number modulus second number and store it in the same variable first number.
  • Loop from 1 to the given second number using the for loop.
  • Multiply the given first number with the iterator value and store it in another variable.
  • Check if the above result modulus second number is equal to 1 using the if conditional statement.
  • If it is true, then return the iterator value.
  • Return 1.
  • Print the modular multiplicative inverse of ‘first number’ under modulo ‘second number’.
  • The Exit of the Program.

Below is the implementation:

# Create a function to say modular_MultInverse which takes the given first and second
# numbers as the arguments and returns the modular multiplicative inverse of
# ‘first number’ under modulo ‘second number’.


def modular_MultInverse(fst_numb, secnd_numb):
  # Calculate the value of the given first number modulus second number and store it in the
  # same variable first number.
    fst_numb = fst_numb % secnd_numb
    # Loop from 1 to the given second number using the for loop.
    for itror in range(1, secnd_numb):
        # Multiply the given first number with the iterator value and store it in
        # another variable.
        mul = (fst_numb * itror)
      # Check if the above result modulus second number is equal to 1 using the if conditional
      # statement.
        if (mul % secnd_numb == 1):
          # If it is true, then return the iterator value.
            return itror
    # Return 1.
    return 1


# Give the first number as static input and store it in a variable.
fst_numb = 10
# Give the second number as static input and store it in another variable.
secnd_numb = 17
# Pass the given first and second numbers as the arguments to the modular_MultInverse
# function.
# Print the modular multiplicative inverse of ‘first number’ under modulo ‘second number'.
print("The modular multiplicative inverse of given first number under modulo second number = ",
      modular_MultInverse(fst_numb, secnd_numb))

Output:

The modular multiplicative inverse of given first number under modulo second number =  12

Method #2: Using For loop (User Input)

Approach:

  • Give the first number as user input using the int(input()) function and store it in a variable.
  • Give the second number as user input using the int(input()) function and store it in another variable.
  • Pass the given first and second numbers as the arguments to the modular_MultInverse function.
  • Create a function to say modular_MultInverse which takes the given first and second numbers as the arguments and returns the modular multiplicative inverse of ‘first number’ under modulo ‘second number’.
  • Calculate the value of the given first number modulus second number and store it in the same variable first number.
  • Loop from 1 to the given second number using the for loop.
  • Multiply the given first number with the iterator value and store it in another variable.
  • Check if the above result modulus second number is equal to 1 using the if conditional statement.
  • If it is true, then return the iterator value.
  • Return 1.
  • Print the modular multiplicative inverse of ‘first number’ under modulo ‘second number’.
  • The Exit of the Program.

Below is the implementation:

# Create a function to say modular_MultInverse which takes the given first and second
# numbers as the arguments and returns the modular multiplicative inverse of
# ‘first number’ under modulo ‘second number’.


def modular_MultInverse(fst_numb, secnd_numb):
  # Calculate the value of the given first number modulus second number and store it in the
  # same variable first number.
    fst_numb = fst_numb % secnd_numb
    # Loop from 1 to the given second number using the for loop.
    for itror in range(1, secnd_numb):
        # Multiply the given first number with the iterator value and store it in
        # another variable.
        mul = (fst_numb * itror)
      # Check if the above result modulus second number is equal to 1 using the if conditional
      # statement.
        if (mul % secnd_numb == 1):
          # If it is true, then return the iterator value.
            return itror
    # Return 1.
    return 1


# Give the first number as user input using the int(input()) function and store it in a variable.
fst_numb = int(input("Enter some random number = "))
# Give the second number as user input using the int(input()) function and store it in
# another variable.
secnd_numb = int(input("Enter some random number = "))
# Pass the given first and second numbers as the arguments to the modular_MultInverse
# function.
# Print the modular multiplicative inverse of ‘first number’ under modulo ‘second number'.
print("The modular multiplicative inverse of given first number under modulo second number = ",
      modular_MultInverse(fst_numb, secnd_numb))

Output:

Enter some random number = 4
Enter some random number = 9
The modular multiplicative inverse of given first number under modulo second number = 7

If you wanna write simple python programs as a part of your coding practice refer to numerous Simple Python Program Examples existing and learn the approach used.