What is the formula for modular exponentiation?

The value computed is (a^b) mod m — a raised to the power b, reduced modulo m. The square-and-multiply algorithm evaluates this in O(log b) multiplications by reading the binary representation of b bit by bit, squaring the base at every step and multiplying the result in only when the current bit is 1.

How does square-and-multiply avoid huge intermediate numbers?

At every multiplication step the value is immediately reduced modulo m, so no intermediate number ever exceeds m minus 1 squared. For a 2048-bit RSA modulus that is roughly a 4096-bit number — enormous by everyday standards, but trivially small compared to the full a^b which would have billions of digits.

What is 4^13 mod 497?

445. The exponent 13 is 1101 in binary. Square-and-multiply walks the bits right to left: bit 1 → multiply; bit 0 → skip; bit 1 → multiply; bit 1 → multiply. Each multiplication reduces mod 497, giving the final answer 445 without ever computing the 8-digit value of 4^13 directly.

Why is modular exponentiation important in cryptography?

RSA encryption and decryption, Diffie-Hellman key exchange, ElGamal, and the Miller-Rabin primality test all reduce to computing (a^b) mod m for very large numbers. The square-and-multiply algorithm makes these feasible in milliseconds even for 2048-bit inputs, while naive exponentiation would require astronomical time and memory.

What is the discrete logarithm and why is it hard?

The discrete logarithm problem asks: given a, target, and m, find the smallest e such that a^e is congruent to target mod m. This is easy to compute in one direction (exponentiation is fast) but believed to be computationally hard to reverse for large m, which is why RSA and Diffie-Hellman are secure.

Is there a limit on how large the inputs can be?

No practical limit. The calculator uses JavaScript BigInt, which supports arbitrary-precision integers. A thousand-bit exponent runs in under a millisecond because the algorithm performs at most 1000 multiplications. The "solve for exponent" panel is limited to modulus 100,000 because that branch uses exhaustive search.

Modular Exponentiation Calculator

A modular exponentiation calculator that computes (a ^ b) mod m correctly and instantly for arbitrarily large inputs, then shows the complete square-and-multiply trace so you can follow every step. It is the right tool for cryptography students, competitive programmers, and anyone checking RSA or Diffie-Hellman arithmetic by hand.

Why ordinary calculators fail here

Suppose you want 2^(2^32) mod 10^9+7. The exponent alone is over four billion. Raising 2 to that power directly produces a number with more than a billion digits — impossible to store in any normal floating-point type. Modular exponentiation solves this by never forming the full power: it keeps every intermediate value below m² throughout the computation.

The square-and-multiply algorithm

The algorithm exploits the binary representation of the exponent:

Step 1. Write b in binary: e.g. 13 = 1101₂.

Step 2. Scan the bits from the least significant to the most significant.

Step 3. At each bit position:

Square the running base: base = base² mod m
If the current bit is 1, multiply the running result: result = result × base mod m
If the bit is 0, skip the multiplication.

Because each multiplication is followed immediately by reduction mod m, the numbers involved never exceed m². For a 1024-bit RSA modulus, that is about 2048 bits — vastly smaller than the raw a^b.

Worked example: 4^13 mod 497

Exponent 13 in binary is 1101.

Step	Bit	Base after squaring	Result after multiply
1	1	4	4
2	0	16	4 (no multiply)
3	1	256	1024 mod 497 = 30
4	1	256² mod 497 = 429	30 × 429 mod 497 = 445

Result: 4¹³ mod 497 = 445. The algorithm did 4 multiplications instead of 12 repeated multiplications, and no intermediate value exceeded 497² = 247,009.

RSA connection

In RSA, encryption is c = m^e mod n and decryption is m = c^d mod n. Both e and d are typically hundreds of bits long, making square-and-multiply the only practical approach. Enter any toy RSA triple into this calculator (try the preset: base = 65, exponent = 17, modulus = 3233) to verify that the result matches the textbook answer.

Solve for the exponent

The amber “Solve for exponent” panel inverts the problem: given base, target, and a small modulus, find the smallest e such that base^e ≡ target (mod m). This is the discrete logarithm — easy to verify, believed to be hard to compute for large m, and the security foundation of Diffie-Hellman and elliptic-curve cryptography.

Everything runs locally in your browser using JavaScript BigInt. No numbers are sent to any server.