how to calculate inverse of modulus function

12 views (last 30 days)
Bhavya K
Bhavya K on 7 Jan 2022
Commented: Bhavya K on 12 Jan 2022
If ax=1mod N , here x is the inverse of a, how to calculate x using matlab?

Answers (1)

John D'Errico
John D'Errico on 7 Jan 2022
Edited: John D'Errico on 7 Jan 2022
The modular inverse you desire exists as long as a and N are relatively prime. If not, then there is a problem. The trick in MATLAB is to use GCD. For example, suppose we wish to compute the modular inverse of 3, mod 7? That is equivalent to solving the problem
mod(3*x,7) == 1
Again, we use GCD. First, read the help for GCD.
help GCD
--- GCD not found. Showing help for gcd instead. --- GCD Greatest common divisor. G = GCD(A,B) is the greatest common divisor of corresponding elements of A and B. The arrays A and B must contain integer values and must be the same size (or either can be scalar). GCD(0,0) is 0 by convention; all other GCDs are positive integers. [G,C,D] = GCD(A,B) also returns C and D so that G = A.*C + B.*D. These are useful for solving Diophantine equations and computing Hermite transformations. Class support for inputs A,B: float: double, single integer: uint8, int8, uint16, int16, uint32, int32, uint64, int64 See also LCM. Documentation for gcd doc gcd Other functions named gcd sym/gcd
Do you see the comment in there about the other return arguments of GCD?
[G,C,D] = gcd(3,7)
G = 1
C = -2
D = 1
The first thing to do is to note that G, thus the GCD, is equal to 1. If it is not equal to 1, then the modular inverse will fail.
Next, see what C and D tell you.
We are told that G = A*C + B*D. So now take the modulas of that expression, with respect to B. If you look carefully, then we see that B*D is a MULTIPLE of B. So, taken mod B, that relation turns into
G = mod(A*C,B)
Do you see it now? The modular inverse of A, taken with respect to B will be the argument C from GCD. Lets try it out.
x = C
x = -2
mod(3*x,7)
ans = 1
So -2, which is congruent to 5, mod 7, is the modular inverse of 3.
Now let me try it on another problem. what is the modular inverse of 6, mod 14?
[G,C] = gcd(6,14)
G = 2
C = -2
Here we seee that G = 2, so NO modular inverse exists in this case. Of course, her e we see the reason why the modular inverse fails, when the GCD (thus G) is not equal to 1. In this example, the result we get is that
2 = mod(6*C,14)
where C = -2, (or if you prefer, 12, since it is all mod 14). There is NO integer you can multiply 6 by, taken mod 14, and get 1 as a result.
Finally, one more example. what is the modular inverse of 134, mod 9937?
[G,C] = gcd(134,9937)
G = 1
C = 3782
X = mod(C,9937) % just in case C was negative, as we saw before
X = 3782
mod(134*X,9937)
ans = 1
The modular inverse will be unique modulo N, IF an inverse exists at all. It should be clear though, that we can add any integer multiple of N to the solution X, and the result will still be a multiplicative inverse modulo N.
Finally, some years ago, I wrote a little toy called modinv. It does the computation I describe above. I've attached it to this answer.

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by