how to calculate inverse of modulus function

If ax=1mod N , here x is the inverse of a, how to calculate x using matlab?

Answer 1

[John D'Errico]

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.

[Bhavya K]

thank you

[Bhavya K]

but modinv doesnot work,

[Bruno Luong]

@Bhavya K works fine to me

a = 134;
p = 9937;
x = modinv(a, p)

x = 3782

mod(a*x, p)

ans = 1

a = 5;
p = 6;
x = modinv(a, p)

x = 5

mod(a*x, p)

ans = 1

[John D'Errico]

@Bhavya K

Of course modinv works. If you think it failed on some specific problem, then you need to show what you did, since I can think of at least a few things you may have done wrong. Off the top of my head...

1. Have you lost the code? Did you download a new release of MATLAB in the last 2 years, but not include modinv in the path for the new release?
2. Did you modify my code? Modified code becomes your code to own and debug. Don't modify provided code, not unless you could have written that code yourself.
3. Did you try to compute the modular inverse for a problem where no modular inverse exists?
4. Did you try to use it on numbers that are too large in magnitude for a double to represent?

I'd bet I could come up with a few other reasons why something would not work. When you say something does not work, you need to say what it did. Telling us that it did not work tells us nothing, since it clearly does work.

twoinv = modinv(2,123456789)

twoinv = 61728395

modinv(2*twoinv,123456789)

ans = 1

Works just fine.

[Bhavya K]

e=5;

modinv(e,24)

Unrecognized function or variable 'modinv'.

Sir I am getting this error. And I am using online matlab R2023b version.I have not modified your code used as it is with same example.

[Sam Chak]

@Bhavya K, I think I understand that you did "not modify @John D'Errico's code" like the following two lines:

e = 5;
modinv(e, 24)

You probably assumed that the modinv() code is a built-in function with MATLAB R2023b.

[Stephen23]

@Bhavya K: take another look at John D'Errico's answer, here is a screenshot of it:

[Bhavya K]

thank you