I'm a high school student writing a paper on RSA, and I'm doing an example with some very small prime numbers. I understand how the system works, but I can't for the life of me calculate the private key using the extended euclidean algorithm.Here's what I have done so far:. I have chosen the prime numbers p=37and q=89 and calculated N=3293. I have calculated (p-1)(q-1)=3168. I have chosen a number e so that e and 3168 are relatively prime.
I'm checking this with the standard euclidean algorithm, and that works very well. My e=25Now I just have to calculate the private key d, which should satisfy ed=1 (mod 3168)Using the Extended Euclidean Algorithm to find d such that de+tN=1 I get -887.25+7.3168=1. I throw the 7 away and get d=-887. Trying to decrypt a message, however, this doesn't work.I know from my book that d should be 2281, and it works, but I can't figure out how they arrive at that number.Can anyone help? I've tried solving this problem for the last 4 hours, and have looked for an answer everywhere. I'm doing the Extended Euclidean Algorithm by hand, but since the result works my calculations should be right.Thanks in advance,Mads.
Rsa Encryption Example
You're so close you're going to kick yourself.3168-887=2281.Specifically, If you have a mod x, then A must satisfy 0.