Modular exponentiation

Summary

Modular exponentiation computes $b^e \bmod m$ for integers $b$, $e \ge 0$ and $m \ge 1$. The binary method writes $e$ in base $2$. It squares $b$ again and again modulo $m$, and it multiplies the squares $b^{2^i}$ for the bits $i$ of $e$ that are $1$. It needs about $2 \log_2 e$ multiplications modulo $m$, and each intermediate number is smaller than $m^2$.