I am struggling with finding the decryption key in this example i am failing on Back substitution I can get euclidean algorithm, i get 1 reminder at the end but then I cant understand how back substitution works here is my example.
p = 61 , q = 59
n = 61 x 59 = 3599
q(n) = 61-1 x 59-1 = 3480
3480x * 2531y=1
3480 = 2531(1) + 949
2531 = 949(2) + 633
949 = 633(1) + 316
633 = 316(2) + 1
And then i try back substitution
1=633-316(2)
1=633-316(949 - 633)
1=633 - 316(949) + 316(633)
after that I should combine the numbers but i dont know which, I have no problems solving a example with smaller number but once it come to 3k+ i have trouble. Could any one kindly explain if im doing it correctly?
Regards,
Wojtek.