Fast Modular Exponentiation

The Problem

Modular arithmetic often requires computing powers such as

a^k \pmod n.

If $k$ is large, direct multiplication is inefficient. For example, computing

7^{1000}\pmod{13}

by multiplying $7$ one thousand times is unnecessary.

Fast modular exponentiation computes powers by repeatedly squaring and reducing modulo $n$ . The method is efficient because it uses the binary expansion of the exponent.

Repeated Squaring

The basic idea is that powers can be built from squares:

a^2,\quad a^4,\quad a^8,\quad a^{16},\ldots

Each term is obtained by squaring the previous one:

a^{2m}=(a^m)^2.

Modulo $n$ , we reduce after each step:

a^{2m}\bmod n = (a^m\bmod n)^2\bmod n.

This keeps the numbers small while preserving the final residue.

Binary Expansion of the Exponent

Every nonnegative integer $k$ can be written in binary:

k=\varepsilon_0+\varepsilon_1 2+\varepsilon_2 2^2+\cdots+\varepsilon_r2^r,

where each digit satisfies

\varepsilon_i\in\{0,1\}.

Then

a^k = a^{\varepsilon_0} a^{2\varepsilon_1} a^{4\varepsilon_2} \cdots a^{2^r\varepsilon_r}.

So one only needs the powers

a,a^2,a^4,a^8,\ldots,a^{2^r}.

The terms corresponding to binary digit $1$ are multiplied together.

Example

Compute

7^{100}\pmod{13}.

First write

100=64+32+4.

Thus

7^{100}=7^{64}7^{32}7^4.

Now compute successive squares modulo $13$ :

7^2=49\equiv10\pmod{13}.

Then

7^4\equiv10^2=100\equiv9\pmod{13}.

Next,

7^8\equiv9^2=81\equiv3\pmod{13}.

Then

7^{16}\equiv3^2=9\pmod{13}.

Next,

7^{32}\equiv9^2=81\equiv3\pmod{13}.

Finally,

7^{64}\equiv3^2=9\pmod{13}.

Therefore

7^{100} \equiv 7^{64}7^{32}7^4 \equiv 9\cdot3\cdot9 \pmod{13}.

Compute

9\cdot3\cdot9=243.

Since

243\equiv9\pmod{13},

we obtain

7^{100}\equiv9\pmod{13}.

Algorithmic Form

Fast modular exponentiation can be written as an iterative algorithm.

Given integers $a,k,n$ , with $k\ge0$ and $n\ge2$ , set

r=1, \qquad b\equiv a\pmod n.

While $k>0$ :

If $k$ is odd, replace

r

rb\bmod n.

Then replace

b

b^2\bmod n.

Finally replace

k

\lfloor k/2\rfloor.

When the process ends, $r$ is congruent to

a^k\pmod n.

The algorithm reads the binary digits of $k$ from right to left.

Correctness

At each stage, the algorithm maintains the invariant that the original power is represented by the current accumulated result and the remaining exponent.

Informally, when the current exponent is odd, one factor of the current base must be moved into the result. When the exponent is even, the base is squared and the exponent is halved.

The identity behind the method is

b^k= \begin{cases} (b^2)^{k/2}, & k\text{ even},\\ b(b^2)^{(k-1)/2}, & k\text{ odd}. \end{cases}

Since congruence respects multiplication, reducing after each multiplication does not change the final residue modulo $n$ .

Efficiency

The direct method requires roughly $k$ multiplications.

Fast modular exponentiation requires only about

\log_2 k

squaring steps, plus one multiplication for each $1$ -digit in the binary expansion of $k$ .

Thus the number of arithmetic steps grows logarithmically in the exponent, rather than linearly.

This is a major improvement. For a very large exponent, such as one with hundreds or thousands of bits, repeated squaring is essential.

Negative Bases

Negative bases cause no special difficulty. One first reduces the base modulo $n$ .

For example,

(-3)^{20}\pmod{11}

can be computed using

-3\equiv8\pmod{11}.

Thus

(-3)^{20}\equiv8^{20}\pmod{11}.

The same repeated squaring method applies.

Large Exponents in Number Theory

Fast modular exponentiation is essential in many number-theoretic algorithms.

It is used in Fermat primality tests, Miller-Rabin primality tests, RSA encryption and decryption, Diffie-Hellman key exchange, elliptic curve methods, and computations with finite fields.

For example, RSA requires computing expressions of the form

m^e\pmod N

where $e$ and $N$ may be very large. Without fast modular exponentiation, such computations would be impractical.

Role in Number Theory

Fast modular exponentiation is the computational counterpart of modular arithmetic. It turns theoretical congruence laws into efficient algorithms.

The central idea is simple: use the binary expansion of the exponent, square repeatedly, and reduce after every step.

This method shows how arithmetic structure can produce efficient computation. In modern number theory, this connection between algebra and algorithms is indispensable.