Modular Exponentiation

Naive a**e is O(e) multiplies and overflows immediately. Binary exponentiation: a^e = (a^{e/2})² when e is even, a · a^{e-1} when odd. O(log e) multiplies.

CSES Exponentiation: a, e ≤ 1e9, mod 1e9+7. You must reduce as you go. JS Number is safe for (a * b) % mod only if a*b < 2^53. 1e9+7 squared is ~1e18, which is over 2^53. Use BigInt in the arena for the real modulus, or keep the teaching mod small. C++ uses __int128 or a careful 1LL * a * b % MOD.

modPow with BigInt — the safe JS version of 1e9+7js

function modPow(a, e, mod) {
  a = ((a % mod) + mod) % mod;
  let base = BigInt(a);
  let exp = BigInt(e);
  const m = BigInt(mod);
  let ans = 1n;
  while (exp > 0n) {
    if (exp & 1n) ans = (ans * base) % m;
    base = (base * base) % m;
    exp >>= 1n;
  }
  return Number(ans);
}

TRACE

3^13. 13 = 1101₂. Accumulate the odd steps.

e=13 odd

ans *= 3 → 3. Square base 3²=9. e=6.

1 / 4

CHECK

Fermat: if p is prime and a is not a multiple of p, a^{p-2} ≡ a^{-1} (mod p). When is this legal?

CHECK

CSES Exponentiation II asks a^b^c mod p (p prime). Why is modPow(a, b^c, p) wrong as written?

Checks 0/2

Next lesson