Modular Exponentiation Calculator

Calculate a^b mod n online. Enter a base, a non-negative exponent, and a positive modulus to find the remainder efficiently. The calculator uses binary exponentiation and repeated squaring, with an optional step-by-step calculation table.

Calculate Modular Power

Try an example

How It Works

a^b mod n

Instead of calculating the potentially enormous value of a^b, the algorithm repeatedly squares the base and reduces intermediate values modulo n.

Example: 3⁴ mod 5 = 81 mod 5 = 1. The calculator obtains the same result using smaller modular operations.

Enter your numbers and select Calculate Result to see the answer and the calculation steps.

What Is Modular Exponentiation?

Modular exponentiation is the process of finding the remainder after raising an integer to a power and dividing by a positive integer. It is written as:

a^b mod n = r

Here, a is the base, b is the exponent, n is the modulus, and r is the remainder. The result is always between 0 and n - 1 when n is positive.

Modular exponentiation is used in number theory, cryptography, computer science, and algorithms involving large integer powers. It is especially useful when the ordinary power would be too large to calculate directly.

How Binary Exponentiation Works

Binary exponentiation, also called exponentiation by squaring, takes advantage of the binary representation of the exponent. It reduces the number of multiplications needed to calculate a power.

Reduce the base modulo n.
Initialize the result to 1 modulo n.
If the current exponent is odd, multiply the result by the current base modulo n.
Divide the exponent by 2, discarding any remainder.
Square the current base modulo n and repeat until the exponent becomes zero.

This method requires a number of iterations proportional to the logarithm of the exponent, rather than the exponent itself. That makes it much more efficient for large powers.

Example: Calculate 7¹³ mod 11

First, reduce the base: 7 mod 11 = 7. The exponent 13 has binary representation 1101.

7² mod 11 = 49 mod 11 = 5
7⁴ mod 11 = 5² mod 11 = 3
7⁸ mod 11 = 3² mod 11 = 9

Since 13 = 8 + 4 + 1, multiply the corresponding powers while reducing modulo 11:

7¹³ mod 11 = (7⁸ × 7⁴ × 7) mod 11
= (9 × 3 × 7) mod 11
= 189 mod 11
= 2

Therefore, 7¹³ mod 11 = 2.

Frequently Asked Questions

1. Can I use a negative base?

Yes. The calculator reduces negative bases to their equivalent non-negative residue before performing modular exponentiation. For example, -7 modulo 13 is equivalent to 6 modulo 13.

2. Can the exponent be zero?

Yes. A nonzero base raised to the power zero is 1. The modular result is 1 modulo n. When n equals 1, the result is 0.

3. Can the exponent be negative?

This calculator accepts only non-negative exponents. Negative modular exponents require a modular multiplicative inverse, which exists only when the base and modulus are relatively prime.

4. Why not calculate the full power first?

Large powers can exceed the available integer range. Repeated squaring reduces intermediate values modulo n, avoiding the need to construct the full power.

5. Is the calculator suitable for cryptography?

It demonstrates modular arithmetic and can handle integer inputs within the server's PHP integer range. It is not a cryptographic implementation and should not be used to generate or protect cryptographic keys.

6. What is the difference between modular arithmetic and modular exponentiation?

Modular arithmetic covers operations such as addition, subtraction, multiplication, and remainders. Modular exponentiation specifically calculates a power modulo an integer. See our Modular Arithmetic Calculator for related calculations.