\( (n, t) \) Number Theory

Fast Powering Algorithm

The mod_exp function calculates modular exponentiation efficiently using the binary exponentiation algorithm. Given three integers a, b, and m, where a is the base, b is the exponent, and m is the modulus, it returns the result of (a^b) % m. The function iterates through the binary representation of the exponent b, updating the result by squaring the base modulo m when encountering a '1' in the binary representation of b, and then multiplying it with the current base modulo m. This approach significantly reduces the number of multiplications needed, making it efficient for large exponents.