What is modular exponentiation?

It is the operation base^exp mod m: raise a base to a power, then take the remainder when divided by m. It is the core operation in RSA encryption, Diffie-Hellman key exchange, and many number-theory algorithms.

Why not just compute base^exp then take the modulus?

For large exponents, base^exp is an astronomically huge number that cannot be stored. Square-and-multiply reduces modulo m after every squaring, keeping every intermediate value smaller than m squared, so the result is found in roughly log2(exp) steps.

How does square-and-multiply work?

It scans the exponent bit by bit. It repeatedly squares a running base value modulo m, and whenever the current exponent bit is 1 it multiplies the result by that running value. This computes the power in logarithmic time.

What inputs are valid?

The base and exponent must be non-negative integers, and the modulus must be a positive integer of at least 1. A modulus of 1 always gives 0. Negative exponents are not supported since the result may not be an integer.

Modular Exponentiation Calculator

Modular exponentiation computes base^exp mod m — and this tool does it the right way, with the fast square-and-multiply algorithm, so even thousand-digit exponents resolve instantly. It is the workhorse behind RSA, Diffie-Hellman, and primality tests.

How it works

Naively computing base^exp first is impossible for large exponents — the number is too big to store. Instead, the modulus is applied after every step:

result = 1
b = base mod m
while exp > 0:
    if exp is odd:  result = (result × b) mod m
    b   = (b × b) mod m       # square
    exp = exp >> 1            # next bit

Because every intermediate value stays below m², and the loop runs only about log2(exp) times, the answer is found extremely quickly regardless of how large the exponent is.

Example and tips

(7^256) mod 13 is computed in just 8 squaring steps and equals 9, even though 7^256 itself has 217 digits. A modulus of 1 always yields 0, since every integer is divisible by 1. Keep the exponent non-negative — negative powers would require a modular inverse, which is a different operation.