The Trick of Exponentiation

The most straightforward way to compute the power of a number is through naive exponentiation. This method involves multiplying the base by itself exponent times.

Here is a simple Python implementation of naive exponentiation:

def naive_exponentiation(base, exponent):
    result = 1
    for _ in range(exponent):
        result *= base
    return result
Copy

While this approach is easy to understand and implement, it has a significant drawback: its time complexity is , where is the exponent. For large exponents, this method becomes inefficient and impractical.

A more efficient approach to exponentiation is known as "Exponentiation by Squaring" or "Fast Exponentiation." This method reduces the number of multiplications needed by taking advantage of the properties of exponents.

The idea is based on the following mathematical principles:

1. If the exponent is even, .
2. If the exponent is odd, .

Here is a Python implementation of exponentiation by squaring:

def fast_exponentiation(base, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        half_power = fast_exponentiation(base, exponent // 2)
        return half_power * half_power
    else:
        return base * fast_exponentiation(base, exponent - 1)
Copy

This method has a time complexity of , making it much more efficient for large exponents compared to naive exponentiation.

Here with the help of dynamic programming, we can remove the recursion as follows,

def fast_exponentiation_dp(base, exponent):
    if exponent == 0:
        return 1
    dp = [1] * (exponent + 1)
    
    for i in range(1, exponent + 1):
        if i % 2 == 0:
            dp[i] = dp[i // 2] * dp[i // 2]
        else:
            dp[i] = base * dp[i - 1]
    
    return dp[exponent]
Copy

In many applications, especially in cryptography, we need to compute the exponentiation result modulo some number. We can use the same logic as Efficient Exponentiation with Exponentiation by Squaring. With one small difference, while exponentiation, we take the modulus in each step.

Here is a Python implementation of modular exponentiation using the fast exponentiation technique:

def modular_exponentiation(base, exponent, mod):
    if mod == 1:
        return 0
    result = 1
    base = base % mod
    while exponent > 0:
        if (exponent % 2) == 1:  # If exponent is odd, multiply base with result
            result = (result * base) % mod
        exponent = exponent >> 1  # Divide exponent by 2
        base = (base * base) % mod  # Square the base
    return result
Copy

This algorithm leverages bit shifts to efficiently handle large exponents and maintains a time complexity of .