Simple question: in order to reduce such huge exponents in modular arithmetic, is repeated squaring used in RSA or is there a better way to implement it?

  • 3
    $\begingroup$ The RSA algorithm doesn't use repeated squaring. However, many implementations of the RSA private key operation do use implementations of modular exponentiation that do use repeated squaring in one form or another. $\endgroup$ – Henrick Hellström Nov 26 '15 at 10:38
  • $\begingroup$ @Henrick Hellström I realise that now thanks, blank moment. Is modular exponentiation the most efficient way to do this though? Are there any other methods which I might want to explore (for a project)? $\endgroup$ – Ali Nov 26 '15 at 10:41
  • 2
    $\begingroup$ See Exponentiation by squaring is the basic algorithm. Most implementations use the CRT method for a 4x speedup compared to computing $m = c^d \pmod n$. $\endgroup$ – CodesInChaos Nov 26 '15 at 11:04
  • 1
    $\begingroup$ And there are some even more advanced tricks for speed ups if you know the exponent in advance (for example in the RSA encryption case). $\endgroup$ – SEJPM Nov 26 '15 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.