Divide and Conquer Exponentiation

We spent a lot of time on the problem of devising an efficeint algorithm for "modular exponentiation".

Algorithm: modexp(a,k,n)
Input : a,k,n where 0 ≤ a < n, k ≥ 0, n > 1
Output: x such that x = a^k mod n
      

Please read the unit notes carefully!