In the previous article, we have discussed Python Program to Find Value of y Mod (2 raised to power x)
Given two numbers n and a prime number, the task is to find the modular multiplicative inverse from 1 to the given number n
The modular multiplicative inverse of an is an integer ‘x’ in such a way that
a x ≡ 1 (mod prime)
Examples:
Example1:
Input:
Given number = 5 Given prime number = 7
Output:
The modular multiplicative inverse from 1 to the given number{ 5 } :
1 4 5 2 3
Explanation:
For 1, modular inverse is 1 as (1 * 1)%7 is 1 For 2, modular inverse is 4 as (2 * 4)%7 is 1 For 3, modular inverse is 6 as (3 * 5)%7 is 1 .. ..
Example2:
Input:
Given number = 9 Given prime number = 11
Output:
The modular multiplicative inverse from 1 to the given number{ 9 } :
1 6 4 3 9 2 8 7 5
Program for Modular Multiplicative Inverse from 1 to n in Python
Below are the ways to find the modular multiplicative inverse from 1 to the given number n in python:
Method #1: Using For Loop (Static Input)
Approach:
- Give the number as static input and store it in a variable.
- Give the prime number as static input and store it in another variable.
- Create a function to say modularmultInverse() which takes the iterator value and the given number as the arguments and returns the modular multiplicative inverse from 1 to the given number n.
- Inside the function, calculate the iterator value modulus given prime number and store it in the same variable iterator value.
- Loop from 1 to the given prime number using the for loop.
- Check if the iterator value multiplied by k (where k is the iterator value of for loop) modulus given prime number is equal to 1 using the if conditional statement.
- If it is true, return the value of k.
- Return -1.
- Loop from 1 to the given number using the for loop.
- Pass the iterator value and the given prime number to the modularmultInverse() function and print it.
- The Exit of the Program.
Below is the implementation:
# Create a function to say modularmultInverse() which takes the iterator value and the
# given number as the arguments and returns the modular multiplicative inverse from 1
# to the given number n.
def modularmultInverse(itrvl, gvn_primenum):
# Inside the function, calculate the iterator value modulus given prime number and
# store it in the same variable iterator value.
itrvl = itrvl % gvn_primenum
# Loop from 1 to the given prime number using the for loop.
for k in range(1, gvn_primenum):
# Check if the iterator value multiplied by k (where k is the iterator value of for loop)
# modulus given prime number is equal to 1 using the if conditional statement.
if ((itrvl*k) % gvn_primenum == 1):
# If it is true, return the value of k.
return k
#Return -1.
return -1
# Give the number as static input and store it in a variable.
gvn_numb = 5
# Give the prime number as static input and store it in another variable.
gvn_primenum = 7
# Loop from 1 to the given number using the for loop.
print(
"The modular multiplicative inverse from 1 to the given number{", gvn_numb, "} :")
for itr in range(1, gvn_numb+1):
# Pass the iterator value and the given prime number to the modularmultInverse() function
# and print it.
print(modularmultInverse(itr, gvn_primenum), end=" ")
Output:
The modular multiplicative inverse from 1 to the given number{ 5 } :
1 4 5 2 3
Method #2: Using For loop (User Input)
Approach:
- Give the number as user input using the int(input()) function and store it in a variable.
- Give the prime number as user input using the int(input()) function and store it in another variable.
- Create a function to say modularmultInverse() which takes the iterator value and the given number as the arguments and returns the modular multiplicative inverse from 1 to the given number n.
- Inside the function, calculate the iterator value modulus given prime number and store it in the same variable iterator value.
- Loop from 1 to the given prime number using the for loop.
- Check if the iterator value multiplied by k (where k is the iterator value of for loop) modulus given prime number is equal to 1 using the if conditional statement.
- If it is true, return the value of k.
- Return -1.
- Loop from 1 to the given number using the for loop.
- Pass the iterator value and the given prime number to the modularmultInverse() function and print it.
- The Exit of the Program.
Below is the implementation:
# Create a function to say modularmultInverse() which takes the iterator value and the
# given number as the arguments and returns the modular multiplicative inverse from 1
# to the given number n.
def modularmultInverse(itrvl, gvn_primenum):
# Inside the function, calculate the iterator value modulus given prime number and
# store it in the same variable iterator value.
itrvl = itrvl % gvn_primenum
# Loop from 1 to the given prime number using the for loop.
for k in range(1, gvn_primenum):
# Check if the iterator value multiplied by k (where k is the iterator value of for loop)
# modulus given prime number is equal to 1 using the if conditional statement.
if ((itrvl*k) % gvn_primenum == 1):
# If it is true, return the value of k.
return k
#Return -1.
return -1
# Give the number as user input using the int(input()) function and store it in a variable.
gvn_numb = int(input("Enter some random number = "))
# Give the prime number as user input using the int(input()) function and
# store it in another variable.
gvn_primenum = int(input("Enter some random number = "))
# Loop from 1 to the given number using the for loop.
print(
"The modular multiplicative inverse from 1 to the given number{", gvn_numb, "} :")
for itr in range(1, gvn_numb+1):
# Pass the iterator value and the given prime number to the modularmultInverse() function
# and print it.
print(modularmultInverse(itr, gvn_primenum), end=" ")
Output:
Enter some random number = 9
Enter some random number = 11
The modular multiplicative inverse from 1 to the given number{ 9 } :
1 6 4 3 9 2 8 7 5
If you are learning Python then the Python Programming Example is for you and gives you a thorough description of concepts for beginners, experienced programmers.