Modular Exponentiation — Fast Powers via Squaring

Algorithm

long modPow(long a, long n, long m) {
  long result = 1;
  a %= m;
  while (n > 0) {
    if ((n & 1) == 1) result = result * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return result;
}

Complexity

O(log n) multiplications. Each modular multiplication O(1) for machine ints, O(k²) for k-word big integers.

Overflow

a·a can overflow long (up to 2·10⁹ * 2·10⁹ > long max). Use Math.floorMod + BigInteger or __int128 in C++.

Applications

RSA, Diffie-Hellman, elliptic curves. Fermat primality. Any modular power computation.