Power Modulo - Implementation

Here's the iterative modular exponentiation:

function powerMod(x, n, m)
    result := 1
    x := x mod m
    while n > 0
        if n mod 2 = 1 then
            result := (result * x) mod m
        x := (x * x) mod m
        n := n / 2
    return result

Time: $O(\log n)$. Space: $O(1)$. You avoid overflow by taking $\bmod m$ after every multiplication. This keeps all intermediate values below $m$.