0
$\begingroup$

I know the inverse of [23] is

[23] * [25] = 575

575 congruent to 1 mod 41

[25] is the inverse

I have started the other one but I am doing something wrong I got

[2] * [41] = [82] = [0]

82 congruent to 0 mod 41

I thought 41 would be the inverse but it is not.

$\endgroup$
  • $\begingroup$ What about $21$, what happens when you multiply by $2$? $\endgroup$ – André Nicolas Nov 16 '15 at 21:20
  • $\begingroup$ it seems like that would work so would 21 be the inverse then? $\endgroup$ – bella Nov 16 '15 at 21:22
  • $\begingroup$ Yes The inverse of $2$ modulo any odd number is easy. $\endgroup$ – André Nicolas Nov 16 '15 at 21:24
  • $\begingroup$ You are welcome. In more general situations, and in particular when the modulus is not small, something systematic like the Extended Euclidean Algorithm needs to be used. $\endgroup$ – André Nicolas Nov 16 '15 at 21:30
2
$\begingroup$

Here is a general method for finding the inverse of $a$ in $Z_n$:

  • Set $x_1=1$
  • Set $x_2=0$
  • Set $y_1=0$
  • Set $y_2=1$
  • Set $r_1=n$
  • Set $r_2=a$
  • Repeat until $r_2=0$:
    • Set $r_3=r_1\bmod{r_2}$
    • Set $q_3=r_1/r_2$
    • Set $x_3=x_1-q_3\cdot{x_2}$
    • Set $y_3=y_1-q_3\cdot{y_2}$
    • Set $x_1=x_2$
    • Set $x_2=x_3$
    • Set $y_1=y_2$
    • Set $y_2=y_3$
    • Set $r_1=r_2$
    • Set $r_2=r_3$
  • If $y_1>0$ then output $y_1$, otherwise output $y_1+n$

And here is an equivalent code in C:

int Inverse(int n,int a)
{
    int x1 = 1;
    int x2 = 0;
    int y1 = 0;
    int y2 = 1;
    int r1 = n;
    int r2 = a;

    while (r2 != 0)
    {
        int r3 = r1%r2;
        int q3 = r1/r2;
        int x3 = x1-q3*x2;
        int y3 = y1-q3*y2;

        x1 = x2;
        x2 = x3;
        y1 = y2;
        y2 = y3;
        r1 = r2;
        r2 = r3;
    }

    return y1>0? y1:y1+n;
}

Calling Inverse(41,2) returns $21$.

Calling Inverse(41,23) returns $25$.

$\endgroup$
  • $\begingroup$ That is an implementation of the Extended Euclidean algorithm. $\endgroup$ – Bernard Nov 16 '15 at 21:50
  • $\begingroup$ @Bernard: Thank you for the enlightenment, I wasn't aware of that (I just used it "as is" during Cryptography course for hw assignments, etc). $\endgroup$ – barak manos Nov 16 '15 at 22:04
  • $\begingroup$ You might be interested in a ‘naive’layout in the form of a table that can be performed by hand, and may be easier to follow for non-programmers. I gave a few examples in some answers, such as this one. $\endgroup$ – Bernard Nov 16 '15 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.