These notes and
closely review Unit 3
Study for exam!
Divide and Conquer Exponentiation
We spent a lot of time on the problem of devising an efficeint
algorithm for "modular exponentiation".
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!