Modular Exponentiation

Algorithms

Modular exponentiation efficiently computes $a^{b} mod m$ using the binary exponentiation method, which reduces the number of multiplications needed.

Algorithm

The algorithm uses the binary representation of the exponent to compute the result in $O (lo g b)$ multiplications instead of $O (b)$ .

Time Complexity

The time complexity is $O (lo g b)$ , where $b$ is the exponent.

Implementation

def modular_exponentiation(base, exponent, modulus):
    """Compute (base^exponent) % modulus using modular exponentiation."""
    result = 1
    base = base % modulus  # In case base is larger than modulus

    while exponent > 0:
        # If exponent is odd, multiply the current base with result
        if (exponent % 2) == 1:
            result = (result * base) % modulus
        
        # Exponent must be even now
        exponent = exponent >> 1  # Divide exponent by 2
        base = (base * base) % modulus  # Square the base

    return result

# Example usage:
base = 3
exponent = 200
modulus = 13
result = modular_exponentiation(base, exponent, modulus)
print("({}^{}) % {} = {}".format(base, exponent, modulus, result))