I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting).
I am using very small numbers, p=47, q=59, n=2773, e=17, ɸ(n)=2668, d=157, which means that I have no problem working out the encryption exponent, my calculator can easily do this, but when I decrypt again, the exponent is 157, which my calculator cannot work out.
What is the best way to perform this calculation? And also if I needed to make the exponent bigger, how would this work? (I would prefer a 'method' rather than a web service, so that I can learn how to do it myself)
Thank you for any help!
Best Answer
For the exponent $157$, you have $x^{157}=(\cdots(x^2)^2)^2x)^2x)^2x)^2)^2x\,$. So, you don’t need to look at numbers any larger than the square of your modulus, if you reduce after every multiplication.