hey guys,
i'm trying to understand the rsa-key-generation(http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Key_generation)
so I started choosing p=13 and q=17
N=p*q, so N=221
now i need φ(N)=(p-1)*(q-1), which is 192
now i need to select e, so that the greatest common divisor of e and φ(N)=192 is 1
I'll choose e=7
Now, to get d, i'll have to use the extended euclidean algorithm.
so, e* d+ k* φ(N)=1 or 7* d+ 192* k=1
now I need d and k
for that I did
φ(N)= x* e+ y
x and y are just two natural numbers ( x, y ∈ ℕ), but x should be as high as possible to keep y small.
so i'll take
1) 192= 27* 7+ 3
according to the extended euclidean algorithm the next thing to do is:
2) 7=2* 3+ 1
and
3) 3=3* 1+0
now we have proven that 1 is the greatest common divisor of e=7 and φ(N)=192
now we need the 2nd equation and chang it to 1= 7-2* 3
after that we can change the 1st equation to 3= 192- 27* 7 to replace the 3 in 1= 7-2* 3, so that we have 1= 7-2*( 192- 27* 7)
1= 7-2*( 192- 27* 7) can be changed to 1= 7 -2* 192-54* 7
and with this we can replace the k in 7* d+ 192* k=1 with -2 because of 1= 7 - 2* 192-54* 7
so k=-2
this example is a task my teacher gave me, and in the solutions there is d=55.
now i could simply solve the equation 7 d -2* 192=1 and i'll get d=55,
but i have no clue how to change the equation 1= 7 -2* 192-54* 7 or 1= 7 -2*( 192- 27* 7) to 1= 55* 7 -2* 192
any help?
+118654 
