Index ¦ Archives ¦ Tags ¦ Learning Progress ¦ RSS

Exponentiation in Modular Arithmetic Made Easy

Estimated read time: 3 minutes


Introduction

The following Python script will by no means provide any useful idea to compete against the RSA algorithm , but it does give you an idea of how a simple technique about reducing the size of an exponent in modular arithmetic can bring you closer to using much larger numbers than the ones you could normally use in the Python interpreter.

The script in action

"""Compute the result of a^b (mod k) by using the exponentiation technique.
The goal here is not efficiency, even though the program is actually pretty
fast: the algorithm is applied manually for demonstration purposes.
Testing on a modest Intel Core i5, having `a` and `b` each set to a random
number containing 2,000 digits and `k` set to a modulo of a number containing
20 digits, results are printed in about 3.3 seconds."""

def binary_remainders(num_b):
    """Take `b` and return the binary equivalent in a list of remainders."""
    remainders = []
    quotient = num_b
    while True:
        prev_quotient = quotient
        quotient //= 2
        remainder = prev_quotient % 2
        remainders.append(remainder)

        if quotient == 0:
            break

    return remainders


def powers_of_two(remainders=None):
    """Return a list of the value of powers of two that form the
    exponent`b`."""
    if remainders is None:
        return None

    powers = []
    for index, remainder in enumerate(remainders):
        if remainder == 1:
            powers.append(2**index)

    return powers


def compute_intermediate_congruences(num_a, num_k, powers=None):
    """Compute all necessary intermediate results of congruence in `mod k` for
    powers of 2 in `powers` to form the number `b`."""
    if powers is None:
        return None

    go_up_to = max(powers)

    intermediate_results = {1: num_a}  # Build dictionary to store all results
    start_value = 2  # First power of two to calculate congruence
    congruence = num_a
    while start_value <= go_up_to:
        # value to use for next power of 2
        congruence = congruence ** 2 % num_k
        intermediate_results[start_value] = congruence
        start_value *= 2

    return intermediate_results


def compute_final_congruence(num_k, powers=None, intermediate_results=None):
    """Take all relevant values from `intermediate_results` matching powers in
    `powers`, multiply them together and calculate this number `mod k` to get
    the final result."""
    if intermediate_results is None or powers is None:
        return None

    # store all required values from `intermediate_results`
    congruent_results = []
    for power in powers:
        for key, value in intermediate_results.items():
            if key == power:
                congruent_results.append(value)

    total = 1
    for result in congruent_results:
        total = result * total  # Multiply all results together

    return total % num_k  # final congruence we are looking for


def compute_congruence(num_a, num_b, num_k):
    """Return `c`, the result of `a^b (mod k)`."""
    num_a = num_a % num_k  # Make sure `a` is smaller than `k`

    # Reduce `b` to list of remainders in binary
    remainders = binary_remainders(num_b)

    # Build a list of the powers of 2 forming `b`
    powers = powers_of_two(remainders)

    # Build a list of necessary intermediate results to reach
    # the value of `b` from powers of 2: finds congruence for
    # smaller powers of 2 and store them in a list.
    intermediate_results = compute_intermediate_congruences(num_a, num_k,
                                                            powers)

    # Multiply all relevant intermediate results `mod k` to get the final
    # congruence of `a^b (mod k)`.
    return compute_final_congruence(num_k, powers, intermediate_results)


if __name__ == '__main__':
    print("We will calculate a^b (mod k). Enter only integers.")
    NUM_A = int(input("Provide `a`: "))
    NUM_B = int(input("Provide `b`: "))
    NUM_K = int(input("Provide `k`: "))

    FINAL_RESULT = compute_congruence(NUM_A, NUM_B, NUM_K)
    print(FINAL_RESULT)

Conclusion

It was very interesting to see how a technique that’s applied manually will work wonders with such large numbers. The Python interpreter can barely calculate numbers with exponents with seven digits or more, while a basic approach like the one shown above can quickly churn out the results for seemingly quite large numbers.

As always, this code is available on GitHub.

© Sébastien Lavoie. Built in Python using Pelican v4.6.0. Theme adapted from Giulio Fidente on GitHub.