Power Modulo Calculator

What Is Modular Exponentiation?

Modular exponentiation is the computation of the remainder when an integer base $a$ raised to an exponent $b$ is divided by a positive integer modulus $m$:

$$a^b \pmod{m}$$

Directly calculating $a^b$ first and then dividing by $m$ quickly becomes impossible on conventional computers because powers grow exponentially. For example, calculating $7^{560}$ produces a number with 474 digits. Modular exponentiation solves this bottleneck by applying the modulo operation at every intermediate multiplication step, keeping numbers manageable and calculations lightning-fast.

The Repeated Squaring Algorithm (Binary Exponentiation)

The most efficient algorithm for modular exponentiation is binary exponentiation, also known as repeated squaring. Instead of performing $b - 1$ multiplications, this method evaluates $a^b \pmod{m}$ in at most $2 \lfloor \log_2(b) \rfloor$ multiplications.

1. Express the exponent $b$ in its binary representation: $b = \sum_{i=0}^{k} b_i 2^i$, where each bit $b_i \in \{0, 1\}$.
2. Compute successive squares modulo $m$: $a^{2^0} \pmod{m}, a^{2^1} \pmod{m}, a^{2^2} \pmod{m}, \dots$.
3. Initialize an accumulator to 1. Whenever bit $b_i = 1$, multiply the accumulator by $a^{2^i} \pmod{m}$ and reduce modulo $m$.
4. When all bits are processed, the accumulator holds the exact result.

Handling Negative Exponents and Modular Inverses

When the exponent is negative, $a^{-k} \pmod{m}$ is interpreted as $(a^{-1})^k \pmod{m}$, where $a^{-1}$ is the modular multiplicative inverse of $a$ modulo $m$.

The modular inverse exists if and only if $a$ and $m$ are coprime, meaning their greatest common divisor is 1: $\gcd(a, m) = 1$. The extended Euclidean algorithm is used to determine this inverse. If $\gcd(a, m) \neq 1$, no modular inverse exists and the calculation cannot be completed in modular arithmetic.

Applications in Cryptography and Number Theory

Modular exponentiation forms the mathematical backbone of modern public-key cryptography:

• RSA Encryption and Signatures: Encryption calculates $c = m^e \pmod{n}$, while decryption computes $m = c^d \pmod{n}$ using large 2048-bit or 4096-bit primes.
• Diffie-Hellman Key Exchange: Shared secrets are derived by computing $g^{ab} \pmod{p}$ from exchanged values $g^a \pmod{p}$ and $g^b \pmod{p}$.
• Fermat Primality Test and Miller-Rabin: Probabilistic prime tests check whether $a^{n-1} \equiv 1 \pmod{n}$ holds for various candidate bases.

You can also explore related tools such as the Modulo Calculator and the Exponent Calculator.