How to perform Multiplicative Inverse Modulo in IDEA How to perform the Multiplicative Inverse Modulo in International Data Encryption Algorithm? I don't understand on how to perform it…

For example, let's say I have a value of cf80 and the value that is appearing to me is this 3080. This is the thing that I've done based on my understanding:

answer = 53120 % 65537  
53120(integer value of 3080) = 3080


When I convert the result in hexadecimal, the value is 3080 but the correct result should be 9194.
Well, the multiplicative inverse of $a$ is defined to be that value $b$ for which $a \times b = 1$, where $\times$ is the multiplication operation in the field/ring/group in question.

Because we're talking about the group of multiplication modulo 65537, that means that the problem is, given $a$, find $b$ such that $ab \bmod 65537 = 1$.

Now, the % operator is C doesn't do it.  The classical way is to use the Extended Euclidean algorithm, where the two inputs to the algorithm is $a$ and $65537$; and have it find a solution to the equation $ax + 65537y = GCD(a, 65537) = 1$; the value $x$ is the multiplicative inverse you're looking for.

Of course, since there are only 65536 possible inverses, another possibility is simply have a table of the 65536 possible inverses, and just do a lookup.  In that case, you can use the Extended Euclidean algorithm to build the table.

Oh, and as a reminder; idea interprets the 0000 bit pattern as the value 65536 as far as multiplication is concerned (as the value 0 doesn't have an inverse).