Thread: RSA Public Key Cryptosystem question

I am trying to work a RSA problem with my two primes of p=17 and q=23 my n = 31

I computed z = p q = 391
(q-1) (p-1) = 352
I need to compute s in n s mod 352 = 1

I have gone through the examples time and time again and can not figure it out. I think I use the Euclidean Algorithm but I am missing something for sure. Any help would be much appreciated.

Hello,

Originally Posted by Frostking

I am trying to work a RSA problem with my two primes of p=17 and q=23 my n = 31

I computed z = p q = 391
(q-1) (p-1) = 352
I need to compute s in n s mod 352 = 1

I have gone through the examples time and time again and can not figure it out. I think I use the Euclidean Algorithm but I am missing something for sure. Any help would be much appreciated.

a=352
n=31
for more convenience

352=31x11+11 --> 11=a-11n

31=11x2+9 --> 9=31-11x2=n-(2a-22n)=23n-2a

11=9+2 --> 2=11-9=(a-11n)-(23n-2a)=3a-34n

9=2x4+1 --> 1=9-2x4=(23n-2a)-4(3a-34n)=159n-14a

1=159x31-14x352

--> 159x31=1 mod 352

s=159