Short intro to Modular exponentiation

In the world of computer science, especially in cryptography, we often need to calculate extremely large numbers. If you have ever wondered how your browser stays secure or how RSA encryption works, you have already encountered modular exponentiation.

In simple terms, modular exponentiation is the process of computing the remainder when an integer $b$ (the base) is raised to the power $e$ (the exponent) and divided by a positive integer $m$ (the modulus). Mathematically, this is written as

$$c=b^e(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

At first glance, this looks like a problem for a standard power function. However, consider trying to compute

$$5^{100} \pmod{7}$$

Standard power functions face two major obstacles. First, there is the issue of overflow. The number

$$5^{100}$$

has more than $70$ digits, and most standard programming data types, such as a $64$-bit integer, will overflow or lose accuracy long before reaching this size. Second, computing the full value of such a massive exponent just to extract a small remainder is an enormous waste of computation. This is where binary exponentiation, also known as the square-and-multiply method, becomes essential.

Instead of multiplying the base $b$ exactly $e$ times, we exploit properties of exponents. The key identities are

$$\text{If } e \text{ is even, then } b^e = (b^2)^{e/2}$$

and

$$\text{If } e \text{ is odd, then } b^e = b \cdot (b^2)^{(e-1)/2}$$

By repeatedly squaring the base and reducing modulo $m$ at each step, we reduce the number of operations from linear time

$$O(e)$$

to logarithmic time

$$O(\log e)$$

This makes it feasible to compute modular powers even when the exponent $e$ has hundreds or thousands of digits.

Let us work through a concrete example:

$$3^{13}(\mathrm{m}\mathrm{o}\mathrm{d}7)$$

First, express the exponent in binary. The number 13 written in base 2 is

$$1101_2$$

which corresponds to the decomposition

$$13 = 8 + 4 + 1$$

This allows us to rewrite the exponentiation as

$$3^{13} = 3^8 \cdot 3^4 \cdot 3^1$$

Next, we compute successive squares, taking the modulo 7 at every step:

$$3^1 \pmod{7} = 3$$
$$3^2 \pmod{7} = 9 \pmod{7} = 2$$
$$3^4 \pmod{7} = 2^2 \pmod{7} = 4$$
$$3^8 \pmod{7} = 4^2 \pmod{7} = 16 \pmod{7} = 2$$

Now we multiply the relevant terms:

$$3^8 \cdot 3^4 \cdot 3^1 \equiv 2 \cdot 4 \cdot 3 = 24 \pmod{7}$$

Finally, we compute the remainder:

$$24 \pmod{7} = 3$$

So the final result is

$$3^{13} \pmod{7} = 3$$

By reducing modulo $m$ at every step, the intermediate values remain small and never grow large enough to overflow memory or slow down computation.

Modular exponentiation forms the backbone of modern digital security. In the Diffie–Hellman key exchange, it enables two parties to establish a shared secret over an insecure channel. In RSA encryption, security relies on the fact that modular exponentiation is computationally easy, while reversing the process (computing discrete logarithms) is believed to be computationally infeasible.