These notes and closely review Unit 3 Section 3.5.

Study for exam!

## 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