What is modular exponentiation?

Modular exponentiation computes a raised to the power b, modulo m. Done naively it would take b minus one multiplications, but exponentiation by squaring does it in about log-base-two of b multiplications: it squares the base to reach a, a squared, a to the fourth, a to the eighth, and so on, and multiplies into the running result only the powers picked out by the binary digits of the exponent. The modulus is applied after every multiplication so the numbers never grow large.

Why does squaring make exponentiation fast?

Each squaring doubles the exponent you have reached: from a you get a squared, then a to the fourth, then a to the eighth. So after k squarings you can represent a to the power two-to-the-k. Since any exponent b is a sum of powers of two (its binary form), you only need to combine the handful of squared bases whose bits are set. That is log-many steps rather than b steps.

Why take the modulus at every step?

Because a to the power b is astronomically large for real inputs, but you only care about it modulo m. Applying the mod after each multiplication keeps every intermediate value below m, so the numbers stay small and the arithmetic stays fast, while the final answer is unchanged because modular arithmetic is compatible with multiplication.

Where is modular exponentiation used?

It is the core operation of public-key cryptography. RSA encryption and decryption, Diffie-Hellman key exchange, and many primality tests all raise very large numbers to very large powers modulo a large modulus. Only fast modular exponentiation makes these feasible, turning what would be an impossible number of multiplications into a few thousand.

Algorithm · Math

Climb in Doubling Jumps.

Don't memorize fast power — watch the exponent climb in doubling jumps. To find a^b mod m you never multiply b times. You square the base to reach a, a², a⁴, a⁸ … — each squaring doubles the reach — and then multiply into the answer only the powers the binary digits of b pick out. That is O(log b) multiplications instead of b, and taking the mod after every step keeps the numbers tiny. It is the engine inside RSA.

square the base · read b in binary · multiply on set bits · mod every step

FAST POWER

Reach a^b in about log b multiplications, not b.

SQUARING

Square the base repeatedly: a, a², a⁴, a⁸ … each step doubles the exponent reached.

BINARY EXPONENT

The bits of b choose which squared powers get multiplied into the result.

MOD EACH STEP

Apply mod m after every multiply so values never blow up.

fastpow.sim — 3¹³ mod 7 · 13 = 1101₂

Ready

Compute 3¹³ mod 7. Since 13 = 1101₂, we need 3¹ · 3⁴ · 3⁸ (the set bits). Press Step: square the base for each bit position and multiply it in only where the bit is 1.

result = 1, base = a; per bit: if bit: result = result·base mod m; base = base² mod m

Result mod 7

0 / 4

Bits done

Every exponent is a sum of powers of two

The whole trick rests on binary. Thirteen is 1101₂ = 8 + 4 + 1, so 3¹³ = 3⁸ · 3⁴ · 3¹. You never need 3², 3³, 3⁵ and the rest — just the powers whose bit is set. And the powers you do need form a doubling ladder you can climb by squaring: 3¹ → 3² → 3⁴ → 3⁸, each rung one multiplication. So you walk the bits of the exponent from the least significant, keep a base that squares each step, and fold it into a running result whenever the current bit is 1. Take mod 7 after every multiply and the base sequence stays small — 3, 2, 4, 2 — never the astronomical 3¹³ = 1 594 323.

Decompose the exponent

b in binary is a sum of powers of two, so a^b is a product of a^(2^i) over the set bits.

Square the base

Start base = a; each step base = base² mod m, giving a, a², a⁴, a⁸ …

Multiply on set bits

If the current bit is 1, fold it in: result = result · base mod m. Skip it if the bit is 0.

Shift to the next bit

b >>= 1 and repeat until b = 0 — about log₂(b) rounds.

Time

O(log b)

Space

O(1)

This example

4 vs 12

Uses

RSA · DH

For 3¹³ the naive method does 12 multiplications; squaring does 4. That gap explodes with size: raising to a 2048-bit exponent, as RSA does, would be an impossible 2²⁰⁴⁸ multiplications naively, but only about 2048 by squaring. This is exactly why public-key cryptography is practical — RSA, Diffie–Hellman key exchange, and Fermat/Miller–Rabin primality tests all lean on fast modular exponentiation. Pair it with the extended Euclidean algorithm for modular inverses and you have the arithmetic core of modern encryption.

Check yourself

1 · How many multiplications does fast power need for a^b?

Squaring reaches a^(2^i) in i steps, and the binary exponent has only about log₂(b) bits — so a handful of multiplications suffice.

2 · What does one squaring do to the power the base represents?

Squaring a^k gives a^(2k), so the exponent you can represent doubles each step — that is the doubling ladder.

3 · Why take mod m after every multiplication?

Modular arithmetic is compatible with multiplication, so applying mod each step keeps numbers below m without changing the result.

Questions

Why is this so important for cryptography?

RSA and Diffie–Hellman raise huge numbers to huge powers modulo a large modulus. Naively that is an impossible number of multiplications; fast modular exponentiation reduces it to roughly the bit-length of the exponent, which is what makes public-key crypto feasible at all.

Recursive or iterative?

Both work. Recursive: pow(a,b) = pow(a, b/2)², times an extra a when b is odd. Iterative: scan the exponent bits, squaring the base and multiplying on set bits. The iterative bit-scan uses O(1) extra space.

What about overflow?

Intermediate products can be as large as (m − 1)², so use a wide integer type (64-bit) or big-integers for cryptographic sizes. Because you mod after each multiply, the stored values themselves always stay below m.

A few squarings beat a million multiplies.

Square the base up the doubling ladder, fold in the powers the binary exponent selects, mod every step — a^b mod m in log time.

← All algorithms Euclidean GCD → Sieve of Eratosthenes → Big-O Cheatsheet →

Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Climb in Doubling Jumps.

Every exponent is a sum of powers of two

Decompose the exponent

Square the base

Multiply on set bits

Shift to the next bit

Check yourself

Questions

A few squarings beat a million multiplies.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Every exponent is a sum of powers of two

Decompose the exponent

Square the base

Multiply on set bits

Shift to the next bit

Check yourself

Questions

A few squarings beat a million multiplies.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.