Power Mod Calculator
Calculate modular exponentiation — aⁿ mod m — instantly. Power mod (modular exponentiation) computes the remainder when a base raised to an exponent is divided by a modulus. Enter your base, exponent, and modulus to get the result, even for very large numbers.
What Is Modular Exponentiation?
Modular exponentiation computes aⁿ mod m — the remainder when the base a raised to the power n is divided by the modulus m. The result always lies between 0 and m-1.
The naive approach — compute aⁿ first, then divide by m — is computationally impossible for large exponents. Consider RSA encryption, where you might need 3²⁰⁴⁸ mod n: that number has nearly 1000 digits. Instead, the fast power mod algorithm (also called binary exponentiation or repeated squaring) applies the modulus at every step:
- aⁿ mod m = ((a mod m)ⁿ) mod m
- (a · b) mod m = ((a mod m) · (b mod m)) mod m
Using these properties, the algorithm squares and multiplies in O(log n) steps, keeping all intermediate values below m² — computationally trivial even for 4096-bit moduli.
How Power Mod Works: Binary Exponentiation Algorithm
The binary exponentiation algorithm works by expressing the exponent in binary. For each bit in the exponent from most significant to least significant:
- Square the current result: result = result² mod m
- If the current bit is 1, multiply by the base: result = result · a mod m
Example: Compute 7¹³ mod 11
13 in binary is 1101. Start with result = 1:
- Bit 1: square → 1; multiply (bit=1) → 7 mod 11 = 7
- Bit 1: square → 49 mod 11 = 5; multiply (bit=1) → 35 mod 11 = 2
- Bit 0: square → 4 mod 11 = 4; no multiply (bit=0)
- Bit 1: square → 16 mod 11 = 5; multiply (bit=1) → 35 mod 11 = 2
Result: 7¹³ mod 11 = 2. Verification: 7¹³ = 96,889,010,407. 96,889,010,407 / 11 = 8,808,091,855 remainder 2. ✓
This took 4 steps instead of 13 multiplications — the efficiency gain grows exponentially with the exponent size.
Applications: Cryptography, Number Theory, and Competitive Math
RSA encryption is the most prominent application. To encrypt a message M with public key (e, n): ciphertext C = Mᵉ mod n. To decrypt: M = Cᵈ mod n. The security of RSA depends on the difficulty of factoring n = p·q, not on the modular exponentiation itself — that part is fast and efficient.
Diffie-Hellman key exchange uses power mod to establish shared secrets over insecure channels. Both parties agree on a prime p and generator g. Alice computes gᵃ mod p, Bob computes gᵇ mod p, and they exchange results. The shared secret is gᵃᵇ mod p, which both can compute but an eavesdropper cannot (discrete logarithm problem).
Primality testing relies on power mod through Fermat's Little Theorem and Miller-Rabin. For a candidate prime p, computing a^(p-1) mod p must equal 1 for all valid bases a. Repeated failures identify composite numbers; this approach scales to 1024-bit numbers in milliseconds.
In competitive programming and discrete math, power mod appears in combinatorics (computing large binomial coefficients mod a prime), modular arithmetic problems, and number theory proofs. If you encounter "compute the answer mod 10⁹+7" in a programming contest, you need fast power mod.
Frequently Asked Questions
What is power mod (modular exponentiation)?
Power mod computes aⁿ mod m — the remainder when aⁿ is divided by m. For example, 3⁴ mod 5 = 81 mod 5 = 1. It is the fundamental operation in RSA encryption, Diffie-Hellman key exchange, and primality testing.
Why not just compute aⁿ and then take mod?
For large exponents, aⁿ becomes astronomically large — impossible to compute directly. The fast power mod algorithm (binary exponentiation) applies mod at each multiplication step, keeping numbers small. It runs in O(log n) multiplications instead of O(n).
How does binary exponentiation (fast power mod) work?
Binary exponentiation uses the fact that a²ⁿ = (aⁿ)² and a²ⁿ⁺¹ = a·(aⁿ)². By writing the exponent in binary and squaring-then-multiplying, you compute aⁿ mod m in O(log n) steps instead of n steps. This makes it feasible even for 2048-bit RSA keys.
What is Fermat's Little Theorem and how does it relate to power mod?
Fermat's Little Theorem states that for a prime p and any integer a not divisible by p: a^(p-1) ≡ 1 (mod p). This means a^n mod p = a^(n mod (p-1)) mod p, drastically reducing large exponents. It is the mathematical basis for RSA's correctness.
How is power mod used in RSA encryption?
RSA encryption computes ciphertext c = mᵉ mod n, where m is the message, e is the public exponent, and n = p·q is the RSA modulus. Decryption computes m = cᵈ mod n using the private exponent d. Both operations are modular exponentiation with 2048-bit or larger numbers.
What is the Miller-Rabin primality test and does it use power mod?
Yes. The Miller-Rabin test checks primality by computing aⁿ⁻¹ mod n for random bases a. If the result is not 1, n is composite. This test runs multiple modular exponentiations and is used by most modern cryptographic libraries to generate large primes.
Can I compute power mod for negative bases or exponents?
For negative bases, the result depends on the sign pattern. For negative exponents, you need the modular inverse (aⁿ mod m where n < 0 = (a⁻¹)⁻ⁿ mod m), which exists only when gcd(a, m) = 1. This calculator handles positive integers; for negative cases, apply modular inverse first.