# RSA: How do I decrypt this?

Sorry if this is asked a lot, I just don't know if there's a specific word for it.

I'm at uni and have a codebreaking exam in a few days, I don't have to do well in it but I want to do as well as I can, but this is really making me struggle.

Here is my work so far, everything's going alright:

Obviously when I try to do the bottom part, any calculator I use says it's invalid or infinite, I understand it's a crazy big number, but I have no idea how to work it out otherwise.

• There is no crazy big number involved in this example, your tool must be able to do modular exponentiation. I would use a programming language, but most likely a math environment can also do it. Isn there one recommended by the course? Apr 30, 2017 at 13:31
• @eckes it's in the screenshot, but if you can't see it, it's 41754^247543 which a calculator refuses, can't even get to the modulus part because of it. :/ Apr 30, 2017 at 13:35
• @PCarr, See crypto.stackexchange.com/q/31559/30150 please. Apr 30, 2017 at 21:03
• Please don't post text as an image. Instead, please copy the text itself and paste it into the edit box. If you're having trouble getting the text formatted like you want, see this help page. May 18, 2017 at 17:20

The efficient calculation of a modular exponentiation is part of the implementation of RSA. I bet this will be part of the course.

You can use a programming language which has a primitive for that, or you can use math packages. The company behind Mathematica offers a online version under the name WolframAlpha:

• I'll look on WolframAlpha then, we did look at it in the course but I'm not very good at maths and it's not an essential module, I still wanna do as well as I can in it, won't be very well though haha. Apr 30, 2017 at 13:47

If you want to do it with hand calculator, you can use exponentiation by squaring, and compute the remainder after each multiplication. (instead of first computing huge powers and only then taking the remainder)

If you have just a simple calculator to do solve this question, you could use the Square-And-Multiply algorithm. I also had exams where I had to use it, using a simple calculator. Have a look here: Square-And-Multiply

For efficient Encryption and decryption in RSA, method of “exponentiation by repeated squaring and multiplication” is used. Please read Section A(page 8) of the paper in which RSA was proposed. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

Another approach is to use Chinese Remainder Theorem with RSA. You can find more details at