Modular exponentiation calculator

How it works

Computing $a^e \bmod n$ by multiplying $a$ by itself $e - 1$ times is hopeless when $e$ has hundreds of digits, and the power itself would be far too large to write down. Square and multiply needs only about two operations per bit of $e$, and reducing modulo $n$ after each one keeps every number below $n^2$.

From the left: write $e$ in binary and start with $a$ for the leading 1. For each next bit, square (which doubles the exponent reached so far), and if the bit is 1, multiply by $a$ (which adds 1). For $e = 117 = (1110101)_2$ the exponents reached are $1, 3, 7, 14, 29, 58, 117$. From the right: keep the powers $a, a^2, a^4, \dots$ by squaring, and multiply into the result those whose bit is 1. A negative exponent means a power of the inverse, $a^{-k} = (a^{-1})^k$, which needs $\gcd(a, n) = 1$.

When $\gcd(a, n) = 1$, Euler’s theorem $a^{\varphi(n)} \equiv 1 \pmod n$ (Fermat’s little theorem $a^{p-1} \equiv 1$ for a prime $p$) allows reducing the exponent modulo $\varphi(n)$ first. Modular powers are the basic operation of RSA, Diffie-Hellman and many primality tests; in real implementations the sequence of squarings and multiplications must not depend on secret bits, or the timing leaks them.