Modular exponentiation

The purpose of modular exponentiation is to compute the value $c$ in equations of the form

$$c \equiv b^e \pmod{n}$$

when $b$, $e$ and $m$ are known (large) values. One of the algorithms to compute the value of $c$ is exponentiation by squaring, also called binary exponentiation or the right-to-left binary method. For this fast algorithm it is required to convert the exponent $e$ to binary notation. Below is an example implementation in Python, followed by an example.

def modular_pow(base, exponent, modulus):
    if modulus == 1:
        return 0

    result = 1
    base = base % modulus
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = pow(base, 2, modulus)
    return result

Example

As an example we compute:

$$5^{24} \bmod 72$$

In order to compute this we first determine the binary representation of the exponent:

$$24 = 11000_2$$

Note that $11000_2$ has a length of 5, this means we only need 5 steps to compute the exponentiation. We start with the following initial values:

$$\begin{aligned} exponent &= 11000_2 \\ result &= 1 \\ base &= 5 \\ \end{aligned}$$

Because the exponent is even, we only perform the square. We then shift the exponent one bit to the right:

$$\begin{aligned} exponent &= 11000_2 \gg 1 \\ &= 1100_2 \\ \\ result &= 1 \\ \\ base &= base^2 \bmod n \\ &= 5^2 \bmod 72 \\ &= 25 \end{aligned}$$

The exponent is even, so we perform the square and shift the exponent one bit to the right.

$$\begin{aligned} exponent &= 1100_2 \gg 1 \\ &= 110_2 \\ \\ result &= 1 \\ \\ base &= base^2 \bmod n \\ &= 25^2 \bmod 72 \\ &= 625 \bmod 72 \\ &= 49 \end{aligned}$$

Again the exponent is even, so we perform the square and shift the exponent one bit to the right.

$$\begin{aligned} exponent &= 110_2 \gg 1 \\ &= 11_2 \\ \\ result &= 1 \\ \\ base &= base^2 \bmod n \\ &= 49^2 \bmod 72 \\ &= 2401 \bmod 72 \\ &= 25 \end{aligned}$$

Now the exponent is odd. In this case we first perform the multiplication of the result. We then square the base again and shift the exponent one bit to the right.

$$\begin{aligned} exponent &= 11_2 \gg 1 \\ &= 1_2 \\ \\ result &= (result \cdot base ) \bmod n \\ &= (1 \cdot 25) \bmod 72 \\ &= 25 \\ \\ base &= base^2 \bmod n \\ &= 25^2 \bmod 72 \\ &= 625 \bmod 72 \\ &= 49 \end{aligned}$$

The last bit of the exponent is always odd. We perform both the multiplication and the square and return the result.

$$\begin{aligned} exponent &= 1_2 \gg 1 \\ &= 0_2 \\ \\ result &= (result \cdot base ) \bmod n \\ &= (25 \cdot 49) \bmod 72 \\ &= 1225 \bmod 72 \\ &= 1 \\ \\ base &= base^2 \bmod n \\ &= 49^2 \bmod 72 \\ &= 2401 \bmod 72 \\ &= 25 \end{aligned}$$

We can now conclude that:

$$5^{24} \bmod 72 = 1$$