Compute an mod m in O(log n). Read the bits of n from the right: every step squares the base; when the current bit is 1 the base is multiplied into the result. Watch the invariant result · basen = aN hold throughout.
| Approach | Multiplications | Note |
|---|---|---|
| Naive loop | O(n) | one multiply per unit of n |
| Binary exponentiation | O(log n) | square-and-multiply |
| squarings | ⌊log₂ n⌋ | one per bit |
| multiplies | popcount(n) | one per set bit |
| Space | O(1) | two registers |
Invariant maintained at the top of every step: result · base^(remaining n) = a^N.
When remaining n reaches 0, result = a^N mod m. The same loop, with matrix multiply instead of
scalar multiply, powers a matrix for fast Fibonacci (see 11-matrix-exponentiation).