1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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, 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
    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$
    – CodesInChaos
    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
    Nov 26, 2015 at 20:16

0

Reset to default

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.