Fast Exponentiation & Modular Arithmetic

RSA encryption, hashing, and every "print the answer modulo 10⁹+7" problem rely on computing aⁿ mod m with a huge n. Multiplying n times is hopeless; squaring gets there in about 60 steps.

intermediate⏱ 10 min read

←Builds on

0Recursion & the Call Stackaⁿ = (a^(n/2))² is a recursion that halves n on each call.9Bit ManipulationThe binary digits of n decide which squares get multiplied in.9GCD & the Sieve of EratosthenesWith a prime modulus, Fermat turns fast powers into a way to divide.

Leads to→

11Rolling Hash & Rabin–KarpA polynomial hash is computed modulo a large prime, with the powers of the base taken mod p.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Arithmetic on a clock

a mod m is the remainder after dividing by m, a value in 0..m−1. Think of a clock: 15 o'clock is 3 on a 12-hour face. The useful fact is that you can reduce at any moment during addition, subtraction and multiplication:

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

So a long product never needs to be big: reduce after every step. Two warnings. Subtraction can go negative in C++ and Java (-3 % 10 == -3), so write ((a - b) % m + m) % m. And division does not work this way. Instead you multiply by an inverse, which we get from fast power below.

02Squaring instead of multiplying

Computing 3^77 as 3·3·3·… takes 76 multiplications; for n = 10^18 that is out of the question. The trick: square repeatedly to get 3^1, 3^2, 3^4, 3^8, …, each one from the previous with a single multiplication. Then write the exponent in binary: 77 = 1001101₂ = 64 + 8 + 4 + 1. Therefore

==3^77 = 3^64 · 3^8 · 3^4 · 3^1==.

Walk the bits of n from the lowest. If the bit is 1, multiply the result by the current power; then square the power and shift n right:

res = 1; while (n) { if (n & 1) res = res * a % m; a = a * a % m; n >>= 1; }

n has about log₂ n bits, and each costs at most two multiplications, so the whole thing is O(log n).

03Why 10⁹ + 7?

When an answer is astronomically large (counting paths, arrangements, subsets), problems ask for it modulo 1 000 000 007. That number is chosen for two reasons:

it is small enough that the product of two residues, below about 10^18, fits in a signed 64-bit integer (max ≈ 9.2·10^18). So a * b % m is safe with long long, but not with int
it is prime, which makes division possible

Dividing by b mod a prime p means multiplying by b's inverse. Fermat's little theorem says b^(p−1) ≡ 1 (mod p) when p does not divide b, so the inverse is b^(p−2) mod p, one call to fast power. That is how you compute binomial coefficients like n! / (k!(n−k)!) modulo p.

04Pitfalls and other uses

Common bugs:

forgetting % m after one multiplication: a single overflow ruins the answer silently
int instead of long long for the product
not reducing the base first: if a ≥ m, do a %= m before the loop
n = 0 should return 1 (and 1 % m when m = 1)

The same squaring idea works for anything you can multiply associatively. Matrix power computes the n-th Fibonacci number in O(log n). The same pattern also answers "apply this permutation n times" and "where am I after n jumps". Whenever a step repeats n times, ask whether you can square it.

Cost at a glance

aⁿ mod m by squaringO(log n)

Naive repeated multiplicationO(n)

Inverse mod prime p (Fermat)O(log p)

Remember

You may take mod after every addition, subtraction and multiplication, but division needs a modular inverse.
Write n in binary, square the base for each bit and multiply it into the result where the bit is 1: O(log n).
10⁹+7 is prime and its residues multiply safely in 64 bits; the inverse of b is b^(p−2) mod p.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Follow the yellow bit from right to left: base keeps squaring, and res only grows where the bit is 1. Compare the multiplication counter with the naive n − 1.

Interactive visualizerfocus here, then space ← →

3^77 mod 1000 · binary digits of n: 77 = 1001101₂

1

2^664

0

2^532

0

2^416

1

2^38

1

2^24

0

2^12

1

2^01

multiplied into rescurrent bit

base = a^(2^k)

3

= 3^1 mod 1000

result res

1

= 3^0 mod 1000

multiplications

0

naive: 76

log

Compute 3^77 mod 1000. Write the exponent in binary: 77 = 1001101₂, 7 bits. Then 3^77 is a product of the powers 3^(2^k) for the bits that are 1.

Pseudocode

 1 res = 1; base = a mod m 2 while n > 0: 3   if n & 1: res = res * base mod m   // this bit is 1 4   base = base * base mod m           // a^(2^k) → a^(2^(k+1)) 5   n >>= 1                            // next bit 6 return res

1 / 1

Check

Three questions. Pick an answer to see why.

Fast power for 2^13 (13 = 1101₂): which powers of 2 get multiplied into the result?

Roughly how many multiplications does fast power need for n = 10^18?

You need (a / b) mod 1 000 000 007. What do you compute?

Practice

Real problems to lock it in, easiest first.

CSESExponentiation beginner↗LeetCodePow(x, n) intermediate↗LeetCodeCount Good Numbers intermediate↗CSESExponentiation II intermediate↗LeetCodeSuper Pow intermediate↗