Modular Arithmetic

The problem

A problem asks you to compute 7^1000000 mod 1000000007. You type 7 ** 1000000 and wait. In Python it eventually returns a number with over 800,000 digits; in Java and C it silently overflows into garbage long before that. Either way you have burned time and memory building a monster of a number, only to throw almost all of it away with one final mod.

The answer you actually want fits in a single 64-bit integer. The trouble is getting there without ever holding the giant intermediate value. This is what modular arithmetic is for — staying small the whole way.

A first attempt

Multiply the base by itself exp times, taking the remainder as you go so the running value never explodes:

def mod_pow_slow(base, exp, mod):
    result = 1
    for _ in range(exp):
        result = result * base % mod
    return result

Taking the mod every step keeps each number small — good. But it still loops exp times. For an exponent of a billion that is a billion multiplications, O(exp) time. We fixed the size problem but not the count problem.

The insight

You do not have to multiply one factor at a time. Any exponent can be built from repeated squaring. Reading the exponent in binary, x^13 = x^8 · x^4 · x^1, and each of x^2, x^4, x^8 is just the previous one squared. So instead of exp multiplications you need about log₂(exp) of them.

Combine that with two facts that let you take the remainder early and often:

(a · b) mod m = ((a mod m) · (b mod m)) mod m
(a + b) mod m = ((a mod m) + (b mod m)) mod m

The result is modular exponentiation by squaring — a billion-step loop becomes about 30 steps, and no value ever leaves the range of the modulus.

How it works

The code

def mod_pow(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

print(mod_pow(7, 1000000, 1000000007))  # 880007888

// BigInt keeps intermediate products exact for large moduli.
function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
  let result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) {
      result = (result * base) % mod;
    }
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}

console.log(modPow(7n, 1000000n, 1000000007n).toString()); // 880007888

// Safe while mod < ~3 billion, so base * base fits in a long.
static long modPow(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Complexity

Each iteration handles one bit of the exponent, so the loop runs ⌊log₂ exp⌋ + 1 times — about 30 iterations for a billion, 60 for a quintillion.

When to use it

Practice

Recap

• Naive powering either overflows or loops exp times — both are unacceptable at scale.
• (a·b) mod m distributes, so you can take remainders early and keep numbers small.
• Exponentiation by squaring reads the exponent's bits for an O(log exp) modular power.