Enter a base (a), exponent (b), and modulus (n) to compute ab mod n — the remainder when a raised to the power b is divided by n. The Power Mod Calculator uses a fast binary exponentiation algorithm to handle large numbers without overflow, returning the modular result along with a step-by-step breakdown.
a^b mod n
--
Base mod n (a mod n)
--
Exponent in Binary
--
Binary Steps Required
--
Modular exponentiation (also called powmod) is the calculation of a^b mod n — raising a base integer to a power, then taking the remainder when divided by the modulus. It is widely used in cryptography (e.g. RSA), number theory, and computer science because it keeps numbers manageable even when exponents are very large.
One efficient method is the binary (square-and-multiply) algorithm: convert the exponent b to binary, then iterate through each bit from most significant to least. For each bit, square the current result mod n, and if the bit is 1, multiply by a mod n. This avoids computing the enormous intermediate value a^b directly.
For large exponents, a^b can be an astronomically large number — impossible to store or compute directly even on modern hardware. The fast modular exponentiation algorithm performs mod n at each step, keeping numbers small throughout and preventing arithmetic overflow.
Fermat's little theorem states that if p is a prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p). This means you can reduce the exponent b modulo (p−1) before computing a^b mod p, dramatically speeding up calculations when the modulus is prime.
Finding the exponent from the result is called the discrete logarithm problem — given a^b ≡ c (mod n), find b. Unlike modular exponentiation (which is fast), the discrete logarithm is computationally very hard for large n, which is the foundation of many cryptographic systems.
Yes, the base can be negative. When a is negative, a mod n is handled by taking the standard mathematical modulo (always a non-negative result less than n). For example, (-3)^2 mod 5 = 9 mod 5 = 4. The exponent and modulus must be non-negative integers.
Modular exponentiation is central to public-key cryptography, including RSA encryption, Diffie-Hellman key exchange, and digital signatures. It is also used in primality testing algorithms (e.g. Miller-Rabin), hash functions, and pseudorandom number generation.
The modulo operation is defined for integers — it returns the remainder after integer division. Fractional bases or exponents don't have a meaningful integer remainder, so the operation requires all inputs (base, exponent, and modulus) to be integers. The exponent must also be non-negative for the standard definition.