A huge power reduced, without the huge power ever existing.
baseexponent mod modulus
Square and multiply, with every step shown.
7^128 mod 13
3
Reached in 8 multiplications, each one reduced back below 13 before the next.
Multiplications used
8
squarings plus the odd-bit steps
A naive loop would use
127
one per unit of the exponent
Digits never built
about 108
the size of the unreduced power
Exponent in binary
10000000
one row below per bit
Square and multiply, most significant bit first
Each bit of the exponent with the squaring it triggers, whether the base was multiplied in, and the running value
Bit
Value
After squaring
Multiplied in?
Running total
8
1
1
× 7
7
7
0
10
—
10
6
0
9
—
9
5
0
3
—
3
4
0
9
—
9
3
0
3
—
3
2
0
9
—
9
1
0
3
—
3
Every row reduces modulo 13 before the next begins, so nothing on this table is ever bigger than 169. That is the whole trick: the answer to a huge power is reached without the huge power existing.
13 is prime and does not divide 7, so Fermat's little theorem gives 7^12 ≡ 1. The exponent only matters modulo 12, which reduces 128 to 8.
Exact on arbitrary-precision integers — this is the operation RSA and Diffie–Hellman are built from, and it has to be exact to be useful.
What this tool shows
7128 has 109 digits. Its value modulo 13 is 3, and getting there takes seven squarings rather than a hundred and twenty-seven multiplications — because each step is reduced back below 13 before the next one starts.
a raised to b, reduced modulo m
The square-and-multiply steps, bit by bit
How many multiplications it took
How many a naive loop would have taken
The size of the power that was never built
When Fermat’s or Euler’s theorem shortens the exponent
One row per exponent bit Multiplications counted The operation RSA runs on Fermat and Euler named
Exact on integers; not a cryptographic implementation.
Updated 7 September 2026 · Works in any browser, no installation
Square repeatedly, reducing after every step, and multiply the base in where the exponent’s binary digits say to. 7128 mod 13 needs seven squarings: 7, 10, 9, 3, 9, 3, 9, 3. The huge power is never built, because 128 is a power of two and each squaring doubles the exponent while the value stays below 13.
At a glance
Formula shown
Square-and-multiply reads the exponent in binary. Start at 1; for each bit, square the running value, and multiply by the base when the bit is 1. Reduce modulo m after every operation, so nothing ever exceeds m\u00b2. The cost is proportional to the number of bits, not to the exponent.
Scenario support
Working through an RSA or Diffie\u2013Hellman example by hand; checking a primality test that uses modular powers; reducing a large power in a number theory exercise.
Educational estimate
Planning support from the values you enter — not professional advice.
How square-and-multiply works
Write the exponent in binary. 13 is 1101, which says a13 = a8 × a4 × a1.
Now build those powers by squaring: a, a², a⁴, a⁸ — three squarings gets you to the eighth power. Multiply together the ones the binary digits selected, and you have a13 in five multiplications rather than twelve.
Reading left to right does the same thing in one pass: start at 1, and for each bit square the running value and multiply by the base if the bit is 1. That is the table on this page, and each row reduces modulo m before the next begins.
The cost is one or two multiplications per BIT of the exponent. A thousand-bit exponent needs roughly fifteen hundred multiplications, not 21000 of them.
Why the naive way is impossible
The obvious approach is to compute ab and then take the modulus. It works for tiny numbers and fails completely past them.
7128 has 109 digits — still storable. 7100000 has about 84,510 digits, and each multiplication towards it is slower than the last. An RSA-sized power would have more digits than there are atoms available to write them on.
Reducing at every step keeps every intermediate below m². That single change turns an impossible computation into an instant one, and it is the reason public-key cryptography is practical at all.
The page reports both counts: the multiplications actually used, and the size of the power you avoided building.
Reducing the exponent, not just the base
Reducing the base modulo m is obviously allowed. Reducing the EXPONENT modulo m is not — and getting that wrong is the commonest mistake in this area.
Fermat’s little theorem. If p is prime and does not divide a, then ap−1≡ 1 (mod p). So the exponent may be reduced modulo p−1, not modulo p. 5117 mod 19 becomes 5117 mod 18 = 59.
Euler’s theorem. For a composite modulus, the same holds with φ(m) in place of p−1, provided a and m are coprime. φ(26) is 12, so an exponent modulo 26 reduces modulo 12.
The page names whichever theorem applies to your inputs and states the reduced exponent, so the shortcut can be checked against the full computation rather than taken on trust.
This is what RSA computes
RSA encryption is one modular exponentiation: ciphertext = messagee mod n. Decryption is another: message = ciphertextd mod n. There is no other operation in it.
The keys are built so that e and d are modular inverses of each other modulo φ(n), which makes the two exponentiations undo one another. The textbook pair 17 and 2753 modulo 3120 is on the inverse page.
Diffie–Hellman is the same operation used differently: both sides compute gsecret mod p, exchange the results, and raise what they received to their own secret. Both arrive at gab mod p without either secret crossing the wire.
What makes this secure is that going backwards — recovering the exponent from the result — is the discrete logarithm problem, and no fast general method for it is known.
Negative and zero exponents
Exponent zero gives 1, for every base and every modulus above 1. The empty product is 1, and no multiplication happens.
A negative exponent means the inverse. a−1 mod m is the number that multiplies a to 1, and a−k is that number raised to k. The page resolves it that way and says so.
It only works when a and m are coprime. If they share a factor there is no inverse, and no negative power exists either — the page refuses with the shared factor named rather than returning something misleading.
A modulus of 1 sends everything to 0, since every integer is congruent to 0 modulo 1. It is a degenerate case, but a real one, and the page answers rather than erroring.
What this page is not
It is a tool for understanding the operation, and it should be said plainly what that excludes.
It is not constant-time. The square-and-multiply shown here branches on the exponent’s bits, which in a real implementation leaks the exponent through timing. Production code uses a ladder that performs the same operations regardless of the bit.
It runs in your browser. Nothing is sent anywhere, but a web page is not where key material belongs. Use it for examples and exercises, not for anything you need to keep.
It is not a cryptographic library. Real RSA needs padding, and unpadded RSA is broken in ways that have nothing to do with the exponentiation being correct.
Sources and methodology
The algorithm and the standards that depend on it are both published — these are the references.
Method. The exponent is read bit by bit, most significant first, and the running value is reduced modulo m after every squaring and every multiplication, so no intermediate exceeds m². The step table is the algorithm’s own trace rather than a reconstruction. The suite checks the result against naive exponentiation — actually building base^exp and reducing it — wherever the power is small enough to build, so square-and-multiply is never trusted against itself. That engine is verified on every change against 69 hand-written assertions, including that the result matches a fully built-out power on four hundred generated cases, and that Fermat’s little theorem holds on every residue of twenty-four primes. The count and the per-case breakdown are published on the formula verification page.
Related calculators
Where this goes next:
ModuloAll three conventions at once, because −7 mod 3 is −1 in JavaScript and 2 in Python and a page that gives only one of those is wrong for half its readers.
Modular InverseThe number that undoes a multiplication modulo n, from the extended Euclidean algorithm — or the shared factor that proves no such number exists.
CoprimeSet coprimality and pairwise coprimality are different conditions: 6, 10 and 15 have gcd 1 and not one coprime pair. Both are reported, with the offending pairs named.
ExponentPowers with the awkward cases right — a negative exponent is a reciprocal not a sign, a fractional one is a root, and zero to the zero is reported as contested.
Prime NumberWhether a number is prime, with a divisor named when it is not and the size of the search stated when it is. Deterministic, not probabilistic.
Chinese Remainder TheoremSolves a system of congruences including the moduli that are not coprime, which most tools refuse — with the merge shown one congruence at a time.
A negative exponent means the modular inverse, and the Modular Inverse Calculator shows where that number comes from — the extended Euclidean algorithm, with the steps.
Educational use disclaimer
This is an educational tool for understanding the operation. It is not a cryptographic library: real key material must not be typed into a web page, and nothing here is constant-time.
Published the modular exponentiation page with the square-and-multiply trace shown bit by bit, so the algorithm is followable rather than magical.
The size of the power that was never built is computed from logarithms rather than asserted, which is what makes the saving concrete.
Fermat's little theorem and Euler's theorem are surfaced when they apply, since reducing the exponent modulo n instead of modulo φ(n) is the commonest mistake in this area.
Add this calculator to your site
Responsive embed — and private: nothing your visitors type leaves their browser.