Lessons from Modular Exponentiation

Four lessons:

$1.$ Binary representation of $n$ determines which powers of $x$ you multiply

$2.$ Taking modulo after every step prevents overflow without changing the final result

$3.$ Iterative version uses $O(1)$ space instead of $O(\log n)$ recursion depth

$4.$ This same technique applies to matrix exponentiation and other algebraic structures

Modular exponentiation is a staple in competitive programming. You'll use it in number theory, combinatorics, and cryptography problems.