Modular Exponentiation Calculator

About Modular Exponentiation Calculator

The Modular Exponentiation Calculator computes \(a^b \bmod n\) — raising a base \(a\) to an exponent \(b\) and taking the remainder when divided by modulus \(n\). It uses the binary exponentiation algorithm (also called fast power or exponentiation by squaring), which reduces the operation from \(O(b)\) multiplications to just \(O(\log b)\). This is the same algorithm used in real-world cryptographic implementations like RSA, Diffie-Hellman, and ElGamal.

Applications of Modular Exponentiation

How the Binary Exponentiation Algorithm Works

The key insight is that we can decompose any exponent into a sum of powers of 2 using its binary representation. For example, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), so \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

The algorithm processes the binary digits of the exponent from left to right:

Pseudocode

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // bit is 1
            result = (result × base) mod mod
        exp = exp >> 1        // shift right (divide by 2)
        base = (base × base) mod mod
    return result

Key Formulas

How to Use the Modular Exponentiation Calculator

1. Enter the base (a): This is the number you want to raise to a power. It can be positive or negative. For example, enter 7 for computing 7^256 mod 13.
2. Enter the exponent (b): This must be a non-negative integer. It represents the power. For cryptographic applications, this can be very large (the calculator supports up to 10^18).
3. Enter the modulus (n): This must be a positive integer. It is the number you divide by to get the remainder. In RSA, this is typically the product of two large primes.
4. Click Calculate: The calculator computes a^b mod n using binary exponentiation and shows the result instantly.
5. Watch the animation: Press Play to watch the binary exponentiation algorithm execute step by step. Each bit of the exponent is processed in sequence, showing whether the algorithm squares, or squares and multiplies.
6. Review the trace: The step-by-step table shows every intermediate computation, and the efficiency comparison shows how much faster binary exponentiation is versus naive repeated multiplication.

Why Binary Exponentiation is Fast

Consider computing \(2^{1000} \bmod 13\). The naive approach requires 999 multiplications. Binary exponentiation converts 1000 to binary (1111101000), which has 10 bits. It needs at most 9 squarings plus a few multiplies for each '1' bit — roughly 15 operations total. That is about 98.5% fewer operations. For cryptographic-scale exponents with hundreds of digits, the difference is astronomical: binary method takes thousands of operations where naive would require more operations than atoms in the universe.

FAQ