{"id":20704,"date":"2021-09-21T09:00:08","date_gmt":"2021-09-21T03:30:08","guid":{"rendered":"https:\/\/python-programs.com\/?p=20704"},"modified":"2021-11-22T18:36:16","modified_gmt":"2021-11-22T13:06:16","slug":"python-program-for-modular-multiplicative-inverse","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-for-modular-multiplicative-inverse\/","title":{"rendered":"Python Program for Modular Multiplicative Inverse"},"content":{"rendered":"
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)<\/a><\/p>\n Given two integers and the task is to find the modular multiplicative inverse of \u2018first number\u2019 under modulo \u2018second number\u2019.<\/p>\n The modular multiplicative inverse is an integer \u2018x\u2019 such that<\/p>\n first number x \u2261 1 (mod second number)<\/p>\n 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.<\/p>\n 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.<\/p>\n Examples:<\/strong><\/p>\n Example1:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n Example2:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n Below are the ways to find the modular multiplicative inverse of \u2018first number\u2019 under modulo \u2018second number’ in python.<\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n If you wanna write simple python programs as a part of your coding practice refer to numerous Simple Python Program Examples<\/a> existing and learn the approach used.<\/p>\n 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 \u2018first number\u2019 under modulo \u2018second number\u2019. The modular multiplicative inverse is an integer \u2018x\u2019 such that …<\/p>\nGiven First Number = 10\r\nGiven Second Number = 17<\/pre>\n
The modular multiplicative inverse of given first number under modulo second number = 12<\/pre>\n
Given First Number = 4\r\nGiven Second Number = 9<\/pre>\n
The modular multiplicative inverse of given first number under modulo second number = 7<\/pre>\n
Program for Modular Multiplicative Inverse in Python<\/h2>\n
\n
Method #1: Using For Loop (Static Input)<\/h3>\n
\n
# Create a function to say modular_MultInverse which takes the given first and second\r\n# numbers as the arguments and returns the modular multiplicative inverse of\r\n# \u2018first number\u2019 under modulo \u2018second number\u2019.\r\n\r\n\r\ndef modular_MultInverse(fst_numb, secnd_numb):\r\n # Calculate the value of the given first number modulus second number and store it in the\r\n # same variable first number.\r\n fst_numb = fst_numb % secnd_numb\r\n # Loop from 1 to the given second number using the for loop.\r\n for itror in range(1, secnd_numb):\r\n # Multiply the given first number with the iterator value and store it in\r\n # another variable.\r\n mul = (fst_numb * itror)\r\n # Check if the above result modulus second number is equal to 1 using the if conditional\r\n # statement.\r\n if (mul % secnd_numb == 1):\r\n # If it is true, then return the iterator value.\r\n return itror\r\n # Return 1.\r\n return 1\r\n\r\n\r\n# Give the first number as static input and store it in a variable.\r\nfst_numb = 10\r\n# Give the second number as static input and store it in another variable.\r\nsecnd_numb = 17\r\n# Pass the given first and second numbers as the arguments to the modular_MultInverse\r\n# function.\r\n# Print the modular multiplicative inverse of \u2018first number\u2019 under modulo \u2018second number'.\r\nprint(\"The modular multiplicative inverse of given first number under modulo second number = \",\r\n modular_MultInverse(fst_numb, secnd_numb))\r\n<\/pre>\n
The modular multiplicative inverse of given first number under modulo second number = 12<\/pre>\n
Method #2: Using For loop (User Input)<\/h3>\n
\n
# Create a function to say modular_MultInverse which takes the given first and second\r\n# numbers as the arguments and returns the modular multiplicative inverse of\r\n# \u2018first number\u2019 under modulo \u2018second number\u2019.\r\n\r\n\r\ndef modular_MultInverse(fst_numb, secnd_numb):\r\n # Calculate the value of the given first number modulus second number and store it in the\r\n # same variable first number.\r\n fst_numb = fst_numb % secnd_numb\r\n # Loop from 1 to the given second number using the for loop.\r\n for itror in range(1, secnd_numb):\r\n # Multiply the given first number with the iterator value and store it in\r\n # another variable.\r\n mul = (fst_numb * itror)\r\n # Check if the above result modulus second number is equal to 1 using the if conditional\r\n # statement.\r\n if (mul % secnd_numb == 1):\r\n # If it is true, then return the iterator value.\r\n return itror\r\n # Return 1.\r\n return 1\r\n\r\n\r\n# Give the first number as user input using the int(input()) function and store it in a variable.\r\nfst_numb = int(input(\"Enter some random number = \"))\r\n# Give the second number as user input using the int(input()) function and store it in\r\n# another variable.\r\nsecnd_numb = int(input(\"Enter some random number = \"))\r\n# Pass the given first and second numbers as the arguments to the modular_MultInverse\r\n# function.\r\n# Print the modular multiplicative inverse of \u2018first number\u2019 under modulo \u2018second number'.\r\nprint(\"The modular multiplicative inverse of given first number under modulo second number = \",\r\n modular_MultInverse(fst_numb, secnd_numb))\r\n<\/pre>\n
Enter some random number = 4\r\nEnter some random number = 9\r\nThe modular multiplicative inverse of given first number under modulo second number = 7<\/pre>\n
\n