Modular Exponentiation Calculator: How to Compute a^b mod n Fast
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
A modular exponentiation calculator earns its keep on a single fact: 71000 is an 846-digit number, and 71000 mod 13 is 9. One of those is a wall of digits your calculator refuses to display. The other is a single character, and getting to it takes ten squarings — not a thousand multiplications, and never a single digit of the giant number in between.
That gap is why every public-key system on the internet is built on this one operation. Below: what actually breaks when you compute ab the obvious way, how square-and-multiply sidesteps it, the two directions the algorithm can run, the shortcut that skips most of the work entirely, and the four ways people arrive at a confidently wrong answer.
The 846-Digit Number a Modular Exponentiation Calculator Never Builds
Ask a spreadsheet for 7^1000 and it returns an error or, worse, 1.02E+845 — a rounded float that has thrown away every digit that matters. Remainders depend on the last digits, and a float keeps only the first fifteen. So the answer you get back is not slightly off. It is meaningless.
The fix is to never let the number grow. Multiplication and remainders commute in the way you’d hope:
Reduce after every single multiplication and the running value never exceeds n². For n = 13 that means nothing bigger than 169 ever appears, no matter how large the exponent is. Try 71000 mod 13 in the tool above and watch the Result column — it stays in single and double digits from the first step to the last. If plain remainders are what you actually need, the modulo calculator handles those on their own, and the exponent calculator covers ordinary powers with no modulus in sight.
Square and Multiply, Traced One Bit at a Time
Keeping values small solves the size problem but not the count problem — ab the naive way still needs b − 1 multiplications, and b in cryptography is routinely a 2048-bit number. The trick is that squaring doubles the exponent for free. From a1 you reach a2, a4, a8, a16 in four moves, and any exponent at all is a sum of those powers of two. That sum is just the binary form of b.
Take 713 mod 11. Thirteen in binary is 1101. Start with the leading 1 bit already consumed, so the accumulator holds 7, then walk the remaining bits — square every time, multiply by 7 whenever the bit is 1:
| Bit | Square | Multiply by 7? | Accumulator |
|---|---|---|---|
| 1 (leading) | — | — | 7 |
| 1 | 7² = 49 ≡ 5 | 5 × 7 = 35 ≡ 2 | 2 |
| 0 | 2² = 4 | no | 4 |
| 1 | 4² = 16 ≡ 5 | 5 × 7 = 35 ≡ 2 | 2 |
713 mod 11 = 2, from three squarings and two multiplications. The naive route needs twelve multiplications, so even on a four-bit exponent the fast method is less than half the work. The saving compounds brutally: the operation count grows with the number of bits in b, not with b itself.
| Exponent b | Bits | Naive multiplies | Square and multiply |
|---|---|---|---|
| 1,000 | 10 | 999 | 14 |
| 1,000,000 | 20 | 999,999 | 25 |
| 109 | 30 | ≈ 109 | ≈ 44 |
| RSA-2048 exponent | 2,048 | ≈ 10616 | ≈ 3,072 |
Read the bottom row twice. A 2048-bit RSA decryption finishes in about three thousand modular multiplications — a few milliseconds. The naive version would need more operations than there are atoms in the observable universe, several hundred times over.
Left to Right or Right to Left: Two Routes, One Answer
Both variants get called square-and-multiply, and textbooks switch between them without warning, which is a reliable source of confusion when your trace does not match the one in the book. Flip the direction selector above and the step table changes completely while the answer does not.
| Left to right | Right to left | |
|---|---|---|
| What gets squared | the running result | the base |
| Values tracked | one | two (result and base) |
| Needs bit length first | yes — must start at the top bit | no — consumes bits as they come |
| Multiplications | one per 1 bit, minus the leading one | one per 1 bit |
| Typical use | textbook proofs, hand calculation | library code, streaming exponents |
Run 713 mod 11 the other way to see how different the middle looks. Reading 1101 from the right, the base gets squared instead of the result: result starts at 1 with base 7, the first 1 bit makes result 7 while the base becomes 5, the 0 bit skips the multiply and the base becomes 3, the next 1 bit takes result to 7 × 3 = 21 ≡ 10 with base 9, and the final 1 bit gives 10 × 9 = 90 ≡ 2. Same answer, 2 — but not one of the intermediate values 7, 10, 5, 3, 9 appeared in the left-to-right table above.
That run cost three squarings and three multiplications against left-to-right’s three and two. The difference is one operation, permanently: left-to-right gets the leading 1 bit for free by starting the accumulator at a, while right-to-left has to multiply it in like any other bit. Nobody chooses between them on that basis. Right-to-left is what almost every real implementation uses, because the loop condition is simply “while the exponent is greater than zero, shift it right” — no bit-length lookup required, and the exponent can arrive one word at a time. Left-to-right is easier on paper, since you only ever track one number.
One warning that matters outside a classroom: both traces branch on the bit value, so the multiplication only happens on 1 bits. An attacker measuring power draw or timing can read the exponent straight off that pattern. Production crypto libraries use constant-time ladders precisely to close that channel. This page is a teaching tool, not a hardening one.
Cutting the Exponent Down With Euler and Fermat
There is a way to skip most of the squarings altogether. Powers modulo n cycle, and the cycle length divides φ(n), Euler’s totient — the count of integers below n sharing no factor with it. When gcd(a, n) = 1, Euler’s theorem says aφ(n) ≡ 1, so the exponent only matters modulo φ(n):
Compute 31000 mod 100 by hand with that. φ(100) = 40, and 1000 mod 40 = 0, so the answer is 30 = 1. No trace, no squaring, one division. The tool reports φ(n) and the reduced exponent in the shortcuts panel whenever it can factor the modulus, and you can look up totients directly with the Euler phi calculator. When n is prime this collapses further into Fermat’s little theorem, φ(p) = p − 1, which is the version most people meet first.
The real cycle length is often shorter than φ(n) — that is the multiplicative order, and the calculator prints it beside φ. For 3 modulo 100 the order is 20, not 40. Both work for reduction; the order just works harder.
Two things have to be true before you use this. Fermat’s theorem also runs in reverse as a primality test, and it is famously imperfect: 2340 mod 341 = 1, which makes 341 look prime, but 341 = 11 × 31. Numbers like that are called Fermat pseudoprimes, and the Carmichael numbers (561 is the smallest) fool the test for every coprime base. If you need to know whether a number is genuinely prime, factor it with the prime factorization calculator rather than trusting a power test. The same exponentiation drives the Lucas-Lehmer test behind the Mersenne prime calculator, which does not have this weakness.
How RSA Becomes Two Calls to the Same Operation
Encryption with RSA is one modular exponentiation. Decryption is one modular exponentiation. That is the entire runtime of the algorithm. Use the standard toy key: p = 61, q = 53, so n = 3233 and φ(n) = 60 × 52 = 3120. Pick e = 17, and d = 2753 because 17 × 2753 = 46,801 = 15 × 3120 + 1.
decrypt: 27902753 mod 3233 = 65
Both are presets in the calculator — run them back to back and watch 65 come home. The reason it works is exactly the theorem from the last section: e and d were chosen so that e × d ≡ 1 mod φ(n), which makes the round trip a1. Anyone who can factor 3233 recovers φ(n), computes d, and reads the message; nobody can factor a 2048-bit n, which is the whole security argument. Notice what the tool does with a large modulus — it reports that φ(n) is unavailable. That message is the security assumption, printed.
Real implementations do not decrypt the way the second line above suggests. Because the private key holder knows p and q, they compute the result modulo each prime separately with much shorter exponents — d mod (p − 1) and d mod (q − 1) — then glue the two halves back together with the Chinese remainder theorem. Each half runs on numbers of half the bit length, and modular multiplication costs roughly the square of the operand size, so the two half-size exponentiations together take about a quarter of the work. In practice that is a 3 to 4 times speedup on every signature and decryption your browser performs.
Diffie-Hellman key exchange runs on the same machinery in the opposite direction. Two parties each pick a secret exponent, publish gsecret mod p, and raise what they receive to their own secret. Both land on gab mod p. Recovering the secret from the public value means solving a discrete logarithm, and no efficient method is known — exponentiation is cheap, undoing it is not.
Four Ways to Get a Confidently Wrong Answer
Reducing the exponent mod n instead of mod φ(n). The base reduces mod n. The exponent does not — it reduces mod φ(n), which is a different number. Computing 5117 mod 19 as 5117 mod 19 = 53 = 125 ≡ 11 gives the wrong result; via φ(19) = 18 and 117 mod 18 = 9 you get 59 ≡ 1, which is correct. Mixing up which modulus applies to which position is the single most common error on this topic.
Applying Euler when the base and modulus share a factor. Try 2100 mod 12. φ(12) = 4 and 100 mod 4 = 0, so the shortcut claims 20 = 1. The true answer is 4. The theorem requires gcd(a, n) = 1, and gcd(2, 12) = 2. Check coprimality first — the calculator prints the gcd and refuses the shortcut when it fails, and the greatest common factor calculator answers the same question standalone.
Overflow in a fixed-width language. In C, Java or Go, multiplying two 64-bit values near 263 wraps silently before you get to apply the modulus, and the wrapped result is still a perfectly plausible-looking number. Keep the modulus under 231 if you are using 64-bit intermediates, or reach for a big-integer type. This page uses BigInt for exactly that reason.
Leaving the result negative. The % operator in most languages returns a negative remainder for a negative left operand, so (−7) % 11 gives −7, not 4. Mathematical convention puts the answer in the range 0 to n − 1. Normalise with ((x % n) + n) % n before you compare anything. The calculator above does this automatically, which is why a negative base still produces a positive result — and if you want to see the binary machinery underneath, the decimal to binary calculator converts any exponent into the bit string the algorithm actually walks.
For the formal statements and the constant-time variants, the Wikipedia article on modular exponentiation covers the algorithm family, and RFC 8017 specifies exactly how RSA uses it in production.
