Using schoolbook multiplication (which has cost $\mathcal{O}(n^2)$) to multiply two $n$-bit numbers)

  • what is the cost of computing an RSA encryption with $e = 3$?
  • What is the cost if $e$ is chosen randomly in the range $\{3, 5, 7, \ldots, \varphi(N) − 1\}$?
  • I've given hints so you can learn. Post your calculations here on the comment so we can check them. – kelalaka Nov 15 at 20:17
  • It was a midterm review. Thanks but it might be a little bit till I come back to this lol. – User Nov 15 at 20:51
up vote 0 down vote accepted

Since this is schoolbook multiplication and homework, I'll give some hints.

Note that, your question is missing an important part, which algorithm we use in the modular exponentiation?

  • We don't have just multiplications due to the exponentiation operation. We also need the modular reduction. See Modular Exponentiation for general detail.

$$ m^e = c \bmod n$$

  • You may apply either taking the exponentiation than modular reduction, which will cause huge intermediate values, or you can use apply multiple and reduction paradigm. For this in general, Exponentiating by Squaring algorithm is used.

  • Now, reduction, in this case, requires modular reduction that. You may or may not add this into your calculations.

  • for the second part, hint; when using the Exponentiating by Squaring we use the bits of the exponent.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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