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$ Commented Nov 26, 2015 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
    Commented Nov 26, 2015 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$ Commented Nov 26, 2015 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
    Commented Nov 26, 2015 at 20:16


Your Answer

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