Recipe

Compute a^b mod n by repeated squaring

Use when: you need $a^b \bmod n$ for an exponent $b$ too large to multiply out one factor at a time by hand

Goal: the value of $a^b \bmod n$ , computed with only about $\log_2 b$ multiplications

Taught in A first look at modular exponentiation

Quick recipe

Write the exponent b in binary
Build the needed powers a^1, a^2, a^4, ... by squaring the previous result and reducing mod n each time
Multiply together exactly the powers matching a 1 in b's binary expansion, reducing mod n as you go

1
Express $b$ as a sum of distinct powers of $2$ -- its binary expansion.

Example

$b=11$ : $11 = 8+2+1$ , so its binary expansion is $1011$ .

⚡ Shortcut

For a small exponent (single digits), skip the binary decomposition entirely: multiply and reduce one factor at a time, $a^1, a^2, a^3, \ldots$ , until you reach $a^b$ .

Why: the powers of $2$ appearing in $b$ 's binary expansion are exactly the exponents Step 2 needs to build, and no others.
2
Starting from $a^1 \bmod n$ , square the previous result and reduce mod $n$ to get the next one.

Example

$a=5$ , $n=13$ : $5^1=5$ , $5^2=25\equiv12$ , $5^4=12^2=144\equiv1$ , $5^8=1^2=1$ . For $b=11=8+2+1$ , no power past $8$ is needed, so squaring stops here.
- $b$ 's binary expansion needs a higher power of $2$ still — keep squaring one more time.
- the highest power of $2$ needed has been reached — stop squaring and move to Step 3.
Why: squaring doubles the exponent every time. That reaches any power of $2$ up to $b$ in about $\log_2 b$ steps. Reducing mod $n$ after every squaring keeps every number along the way small.
3
Take only the powers from Step 2 whose exponent matches a $1$ in $b$ 's binary expansion. Multiply them together one pair at a time, reducing mod $n$ after each multiplication.

Example

$b=11=8+2+1$ : $5^{11}=5^8\cdot5^2\cdot5^1\equiv1\times12\times5\pmod{13}$ . $1\times12=12$ ; $12\times5=60\equiv8$ .

Why: multiplying exactly the powers of $2$ that sum to $b$ rebuilds $a^b$ from the pieces built in Step 2. It never forms any exponent larger than $b$ itself.

Common mistakes

Forming the full power $a^b$ before reducing, which explodes past anything computable once $b$ is realistically sized.
Reducing only at the very end of a squaring chain instead of after every individual squaring.
Misreading which powers of $2$ b's binary expansion actually needs, and multiplying in an extra or a missing piece.
Reusing a stale squared value instead of recomputing it from the correctly reduced previous power.