Modular Exponentiation

A tough challenge that requires Efficiency in Algorithms:

Given large numbers $a$, $n$, $m$, compute $a^{2}modm$. (This is a challenge in RSA Algorithm)

A (fast) method for solving:

Note it’s easy to compute $e=a^n\mathrm{mod}m$ if we’ve already computed $d=a^{n/2}$

• If n is even, take $e=(d\times d)\mathrm{mod}m$
• if n is odd, take $e=(d\times d\times a)\mathrm{mod}m$
  Thus this is a Recursive Algorithm solution.