MODAR02 - Editorial

editorial
, , ,
1

Problem Link - ModEx Suite in Number theory

Problem Statement:

Given three integers a, b, and m, find a^b mod m.

Approach:

  • Your code implements the efficient calculation of a^b mod m using modular exponentiation (also known as “exponentiation by squaring”). This approach is optimal for computing large powers under a modulus.
  • See how to calculate modular exponentiation: ModEx Suite in Number theory

Complexity:

  • Time Complexity: * The loop in modexp runs while b > 0, and the number of iterations is proportional to the number of bits in b. Since b is reduced by half each time (b>>=1), the number of iterations is O(log⁡ b)
  • Space Complexity: O(1) No extra space needed.