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$.

Remarks

The method is correct because of compatibility with multiplication: one can reduce modulo $m$ after each multiplication. The Fermat primality test, the RSA cryptosystem and the Diffie–Hellman key exchange all use modular exponentiation. The inverse problem, to find $e$ from $b$, $m$ and $b^e \bmod m$, is the discrete logarithm problem. It seems much harder.

Explanations

L1 human

To compute $3^{13} \bmod 7$, write $13 = 8 + 4 + 1$. The squares are $3^1 \equiv 3$, $3^2 \equiv 2$, $3^4 \equiv 4$ and $3^8 \equiv 2$. Then $3^{13} \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3 \pmod 7$. You never need the large number $3^{13} = 1594323$.