Algorithm of the day -

The Fast Modular Exponentiation Algorithm

Summary

A method for efficiently calculating the value of a number raised to a power, modulo another number, often used in cryptography and coding theory

Use Case

Secure online transactions rely on fast modular exponentiation to quickly verify digital signatures and perform other cryptographic operations

Steps

  1. Choose a base, exponent, and modulus as input
  2. Convert the exponent to binary and iterate over each bit
  3. For each bit, square the current result and take the modulus if the bit is 0, or multiply the current result by the base, square it, and take the modulus if the bit is 1
  4. Return the final result after all bits have been processed

Complexity

The time complexity of this algorithm is O(log(n)) and the space complexity is O(1), where n is the exponent

Code Example

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