Power Modulo - Walkthrough

Let me trace $powerMod(3, 13, 1000)$:

Binary of 13: $1101_2$. Process bits right to left.

$1.$ $n = 13$ (odd), $result = 1 \times 3 = 3$, $x = 3^2 \bmod 1000 = 9$, $n = 6$

$2.$ $n = 6$ (even), $result = 3$, $x = 9^2 \bmod 1000 = 81$, $n = 3$

$3.$ $n = 3$ (odd), $result = 3 \times 81 = 243$, $x = 81^2 \bmod 1000 = 561$, $n = 1$

$4.$ $n = 1$ (odd), $result = 243 \times 561 = 136323 \bmod 1000 = 323$

Final answer: $323$. You computed $3^{13} \bmod 1000$ in just $4$ steps instead of $13$ multiplications.