Find the Modular Multiplicative Inverse of an Integer a and Modulo m.
Answer
Learn about Modular Multiplicative Inverse (Inverse Modulo)
The modular inverse is a mathematical operation commonly used in discrete math and cryptology. The formula is as follows: Basically, the modular inverse of a number A mod n is the number x in which: It is a tedious algorithm to do, whether you're going the naive route, or using the Extended Euclidean Algorithm. Use our calculator to make it easier for you!
To solve for a modular inverse, you primarily use the Extended Euclid Algorithm. However, for simplicity purposes, we will be using the naive method. Please note that this method is not feasible for large numbers, hence why it is "naive". To show the method, we can try finding the modular inverse of the following numbers.First, remember what we are actually looking for when we seek the inverse mod. In this case, x is the number we are looking for, A is 5 and n is 26. So how do we actually go about finding x? The naive method will help us. Starting from 0 and going up to n-1, multiply each number from 0 to n-1 by A. For this problem, you will multiply each number between 0 to 25 (inclusive) by 5. What we are doing is guessing what value x could have, and collecting a list of potential i values. As you can see from this example, as A gets larger this method becomes extremely time consuming, so only use this strategy on small numbers A.After multiplying each number, go through the list and check if each potential i value mod 26 = 1. Since 105 mod 26 = 1 and 5 x 21 = 105, the mod inverse of 5 mod 26 is 21. Now, try it yourself!
Multiply each number between 0 to 6 (inclusive) by 3.Go through the values you just creative and check if each potential i value mod 7 = 1. Since 15 mod 7 = 1 and 5 x 3 = 15, the mod inverse of 3 mod 7 is 5. Multiply each number between 0 to 5 (inclusive) by 2. Go through the values you just creative and check if each potential i value mod 6 = 1.There is no modular inverse, since no number between 0 to 5 satisfies the equivalency.
Watch detailed video tutorials about Modular Multiplicative Inverse (Inverse Modulo)!
Extended Euclidean Algorithm and Inverse Modulo Tutorial
6 minutes
How To Find The Inverse of a Number (mod n)
11 minutes
On Demand Computer Science Theory Education for Students.