modular_exponentiation.py

# This script calculates the modular exponentiation of a number using the method of exponentiation by squaring.
# Python has a plain function for this: pow(base, exp, mod)
# This script demonstrates how to implement it manually for educational purposes.

import sys

def main():
    base = int(sys.argv[1]) if len(sys.argv) > 1 and int(sys.argv[1]) > 0 else 11
    exponent = int(sys.argv[2]) if len(sys.argv) > 2 and int(sys.argv[2]) > 0 else 99
    residue_class = int(sys.argv[3]) if len(sys.argv) > 3 and int(sys.argv[3]) > 0 else 15
    answer = calculate_representative(base, exponent, residue_class)
    print("Result: ", answer)
    python_answer = pow(base, exponent, residue_class)
    if answer == python_answer:
        print("Success: Matches Python's built-in pow function.")
    else:
        print("FAIL: Does NOT match Python's built-in pow function: ", python_answer)

def calculate_representative(base:int = 193, exponent:int = 25, residue_class:int = 251) -> int:
    powers = exponent_as_prime_factorization(exponent)
    iterations = max(powers)
    index_values = calculate_power(base, residue_class, iterations, powers)
    print("Multiplication classes:", index_values)
    result = calcResult(index_values, residue_class)
    return result

def exponent_as_prime_factorization(exp:int) -> list[int]:
    powers:list[int] = []
    remain_exp = exp
    while(remain_exp > 0):
        power = 0
        while(pow(2, power+1) <= remain_exp):
            power += 1
        
        remain_exp -= pow(2, power)
        powers.append(power)
    print("exponent list: ", powers)
    return powers

def calculate_power(base:int, residue_class:int, iterations:int, powers:list[int]) -> list[int]:
    calculationValues:list[int] = []
    value = base
    for i in range(iterations):
        value = pow(value, 2) % residue_class
        if(i+1 in powers):
            calculationValues.append(value)
    if(0 in powers):
        calculationValues.append(base)
    return calculationValues

def calcResult(values:list[int], residue_class:int) -> int:
    result = 1
    for i in values:
        result *= i
    return result % residue_class

main()