Does anyone know the code for finding the inverse mod
Here's the math.
Take: e mod n = 1
To get the inverse, there is a value s such that ABS(s*e-t*n)=1
89 mod 160 = 1
ABS(9*89-5*160)=1
9 is the inverse of 89 mod 160
I can do the math, but I need help to code it.

You sure that 9 and that 5 are uniques?

RB

Uhm, 89 mod 160 == 89.
I think you meant that GCD(89, 160) = 1 (GCD = Greatest common divisor).
I'll be assuming that this is the case for the integer math. (btw, if you can do the math, you can code it :-)
GCD(89, 160) = 89*a + 160*b for some (a, b). This is a fundamental property of the GCD.
But you still need to solve for a and b.
Let the equation 89a + 160b = 1.
Firstly, you need to find a particular solution of that equation. We do this using Euclid's algorithm.
code:
160 = 1 * 89 + 71 <=> 71 = 160 - 89
89 = 1 * 71 + 18 <=> 18 = 89 - 71 = 2 * 89 - 160
71 = 3 * 18 + 17 <=> 17 = 71 - 3 * 18 = 4 * 160 - 7 * 89
18 = 1 * 17 + 1 <=> 1 = 18 - 17 = 9 * 89 - 5 * 160

So there you have it. 1 = 89 * 9 - 160 * 5
But this solution isn't unique. In fact, there are infinit number of solutions. For example, 169 and -94 are also solutions. (89 * 169 - 94 * 160 = 1)
But before we discuss that, we have to write an algorithm to do the above. It's simple if you just keep track of the coefficients and sum them up.
You always have an equation of the type:
c = d * q + r, with r the remainder of c / d, q is the quotient. (Warning: This has to be the Euclidian remainder, NOT the result of the % operator!).
At first, c and d are your original numbers (89 and 160 here).
From that equation, you get that: r = 1 * c - d * q. (keep track of the 1 and -q)
You then itterate by setting c <- d and d <- r until r == 1.
If you must need source code, there's a Java applet here: http://users.erols.com/eweidaw/applets/EuclidExtensionApplet.java
Now, we discuss the un-uniqeness of the solution. There are an infinit couple of interger numbers that will satisfy your equation.
However, you do know that;
code:
89a + 160b = 1
and
89 * 9 - 5 * 160 = 1

this implies that: 89(a - 9) + 160(b + 5) = 0
(substracting one from the other)
Thus: 89(a - 9) = 160(-b - 5)
But GCD(89, 160) = 1 so by Gauss's theorem, 160*k = a - 9, thus a = 160k + 9, for any integer k.
Insert this back in the original equation and get that b = -89k - 5 (the same k as the line above!)
Set k to 1 and get my example for an alternate solution.
(edit: spelling, presentation)
[ May 12, 2001: Message edited by: Bob ]

What is inverse mod used for?

Gnudutch:
RSA data encryption/decryption
p and q are any two prime numbers
e is a value that is relatively prime to (p-1)*(q-1)
or GCD(e,(p-1)*(q-1))=1
e is our encryption value
d is our decryption value
d is the inverse of e mod (p-1)((q-1)
Bob:


I meant gcd not mod
gcd(89,160)=1
inverse of 89 mod 160 = 9
I know all the rest, I just wanted a simple bit of code to find the inverse. And I allready figured it out.
-------------------------------------------

Also, I need to be able to mod a large value, but the computer is limited.
example:
p=11;
q=17;
e=89; // encryption key
d=inverse of 89 mod 160 = 9
9*89-5*160=1
Bob:
969*89-539*160=1
969 is also an inverse, but we want the smallest possible. So 9 will suffice.

00 01 02 ... 23 24 25
A B C ... X Y Z
Y = 24:
M=C^e mod n;
M=24^89 mod 187
M=61;
vice-verse
C=M^d mod n
C=61^9 mod 187
C=Y
My problem is that 61^9 is too large
If I knew the value was nine, I could write the code as
61^9 mod 187 = ((61^3 mod 187)^3 mod 187)
because
(a*a) mod n = ((a mod n)*(a mod n)) mod n
Now what if I needed 24^89 mod 187?
[ May 12, 2001: Message edited by: DanielH ]