0
$\begingroup$

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:

screenshot

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – eckes
    Apr 30, 2017 at 13:31
  • $\begingroup$ @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. :/ $\endgroup$
    – P Carr
    Apr 30, 2017 at 13:35
  • 2
    $\begingroup$ @PCarr, See crypto.stackexchange.com/q/31559/30150 please. $\endgroup$
    – Meysam Ghahramani
    Apr 30, 2017 at 21:03
  • $\begingroup$ 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. $\endgroup$
    – Ilmari Karonen
    May 18, 2017 at 17:20

4 Answers 4

Reset to default
1
$\begingroup$

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:

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – P Carr
    Apr 30, 2017 at 13:47
4
$\begingroup$

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)

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

  1. Using CRT with RSA
  2. CRT example in RSA
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.