Modular Exponentiation Explained: Computing a^b mod m Without Overflow

Modular exponentiation is the operation a^b mod m: raise a base to an exponent, then take the remainder when divided by a modulus. It sounds like two ordinary steps glued together, and for tiny numbers it is. But the moment the exponent grows past a few thousand, the naive "compute the power, then take the remainder" approach falls apart completely. The fix is an algorithm called square-and-multiply, and once you understand it, RSA and Diffie-Hellman stop looking like magic.

This post walks through what the operation computes, why you cannot just calculate a^b first, how square-and-multiply cuts the work down to about log2(b) steps, and a full worked example you can check by hand or with the modular exponentiation calculator.

Why you cannot just compute a^b first

The intuitive plan is: calculate a to the power b, get one big number, divide by m, keep the remainder. Mathematically that is the correct answer. Practically it is hopeless.

The problem is size. Exponents make numbers grow at a terrifying rate. Take 7^256. That single value already has over 200 decimal digits. A real RSA private exponent runs around 2048 bits, and a raised to that power would have more digits than there are atoms in the observable universe. No computer can store that number, let alone divide it. The calculation does not run slowly; it runs never.

The escape is one fact from modular arithmetic: you can take the remainder at any point along the way, not just at the end.

(x * y) mod m  ==  ((x mod m) * (y mod m)) mod m

Because multiplying first and reducing later gives the same answer as reducing first and multiplying later, you are free to apply mod m after every single multiplication. That keeps every intermediate value below m. A 2048-bit RSA operation never holds a number larger than a few hundred bytes the whole way through. Reducing as you go is not an optimization layered on top of the real method. It is the method.

Square-and-multiply: log b steps instead of b

Reducing mod m solves the size problem, but there is a second problem: speed. Computing a^b by multiplying a into a running product b times means b multiplications. For b = 65537 (a common RSA public exponent) that is 65,536 multiplications. For a 2048-bit exponent it is astronomically more.

Square-and-multiply (also called fast exponentiation or binary exponentiation) replaces that linear count with a logarithmic one. The trick is to read the exponent in binary and repeatedly square the base.

Here is the concrete payoff: square-and-multiply reduces the number of multiplications from b down to about log2(b). An exponent of 65537 needs roughly 17 squarings instead of 65,537 multiplications. That is not a small speedup, it is the difference between instant and impossible.

The idea: to compute a^13, write 13 in binary as 1101. The set bits tell you which powers to combine. You build up a, a^2, a^4, a^8 by squaring each previous result, then multiply together the ones whose bit is 1:

a^13 = a^8 * a^4 * a^1   (because 13 = 8 + 4 + 1, binary 1101)

Four squarings to reach a^8, plus a couple of multiplies to combine them. That is it. And after every squaring and every multiply, you take mod m, so the numbers stay small the entire time. The step count grows with the number of bits in the exponent, not with the exponent's value, which is the whole insight the algorithm is built on.

A worked example: 3^200 mod 50

Let me trace one all the way through so the abstract description has something to stand on. We want 3^200 mod 50.

First, why not the naive way? 3^200 is a 96-digit number. Writing it out and dividing by 50 is busywork no one should do. Instead, reduce as we square.

The exponent 200 in binary is 11001000. We square repeatedly, reducing mod 50 each time:

| Power | Raw value | mod 50 | |-------|-----------|--------| | 3^1 | 3 | 3 | | 3^2 | 9 | 9 | | 3^4 | 9^2 = 81 | 31 | | 3^8 | 31^2 = 961 | 11 | | 3^16 | 11^2 = 121 | 21 | | 3^32 | 21^2 = 441 | 41 | | 3^64 | 41^2 = 1681 | 31 | | 3^128 | 31^2 = 961 | 11 |

Now 200 = 128 + 64 + 8, which matches the set bits in 11001000. Multiply those three powers, reducing as we go:

3^200 mod 50 = (3^128 * 3^64 * 3^8) mod 50
             = (11 * 31 * 11) mod 50
             = (341 * 11) mod 50
             = (41 * 11) mod 50      (341 mod 50 = 41)
             = 451 mod 50
             = 1

So 3^200 mod 50 = 1. Eight squarings and two multiplies, every number kept under 50, no 96-digit monster anywhere. You can paste 3, 200, and 50 into the calculator's step view and watch the same residues appear.

Where this powers real cryptography

This single operation is the engine room of public-key cryptography. Once you see it, you start spotting it everywhere.

RSA. Encryption is c = m^e mod n and decryption is m = c^d mod n. Both directions are nothing but modular exponentiation. The security rests on the fact that this is fast to compute forward but, without the private exponent, hard to reverse.

Diffie-Hellman key exchange. Each party computes g^secret mod p and exchanges the result. The square-and-multiply structure makes it cheap to compute your public value, while recovering the secret from it (the discrete logarithm problem) is believed to be intractable.

Miller-Rabin primality testing. The probabilistic test used to find the large primes RSA needs is built on repeated modular exponentiation. Without fast exponentiation, generating an RSA key would take longer than you would care to wait.

Every public-key scheme that leans on factoring or the discrete logarithm leans, underneath, on this one operation being fast to do and hard to invert.

A note from working with it

The first time I implemented modPow from scratch, in C, my small test cases all passed and I shipped it feeling clever. Then a colleague fed it a 1024-bit modulus and got garbage. The bug was embarrassing in hindsight: I had remembered to reduce mod m after each squaring but forgotten to reduce after the multiply step that combines the set-bit powers. With tiny inputs nothing overflowed, so the missing reduction never mattered. With real cryptographic numbers, the intermediate product blew straight past 64 bits and wrapped silently. The lesson stuck: reduce after every multiplication, not just most of them. When I'm sanity-checking a routine now, I paste the same base, exponent, and modulus into a BigInt reference, turn on the step view, and compare intermediate values line by line until I find exactly where mine diverges.

Common pitfalls

A few traps worth naming before you go:

Computing a^b first. For any real cryptographic size this overflows or freezes. Always reduce at every multiply.
Assuming negative exponents always work. a^(-b) mod m exists only when the base is coprime to the modulus, because it needs the modular inverse. 4^(-1) mod 6 is simply undefined.
Modulus 1 surprises. It is valid but always returns 0, since every integer is congruent to 0 mod 1, even a^0.

If you want to go deeper into the number theory underneath, the related building blocks are worth a look: the GCD and LCM calculator shows the greatest-common-divisor check that decides whether a modular inverse exists in the first place, which is exactly the gate behind negative exponents.

Modular exponentiation is one of those rare ideas that is both genuinely deep and genuinely simple once the binary trick clicks. Reduce as you go, square instead of multiply, and a calculation that looked impossible finishes in a blink.

Made by Toolora · Updated 2026-06-13