Modular Exponentiation Calculator
Modular exponentiation computes a^b mod m: the remainder when a raised to the power b is divided by m. This operation is the computational backbone of public-key cryptography, including RSA and Diffie-Hellman key exchange, because computing a^b for large b directly produces numbers with millions of digits. The binary exponentiation algorithm solves this by repeatedly squaring the base and reducing modulo m at each step, keeping all intermediate results small. The result is always a non-negative integer less than m. Enter integers a (base), b (exponent, non-negative), and m (modulus, positive) to compute the result.
Binary exponentiation algorithm
result = 1; base = a mod m
while b > 0: if b is odd, result = (result * base) mod m; base = (base * base) mod m; b = b / 2
This square-and-multiply method requires only O(log b) multiplications and never needs to compute a^b directly. Each squaring step reduces the intermediate value with mod m, ensuring numbers stay manageable.
Applications of modular exponentiation
- RSA encryption: ciphertext c = plaintext^e mod n; decryption: plaintext = c^d mod n.
- Diffie-Hellman: compute g^x mod p for shared key derivation.
- Fermat's primality test: check a^(p-1) mod p = 1 for prime candidate p.
- Miller-Rabin primality test: based on modular exponentiation with several bases.
- Computing Fibonacci numbers modulo m efficiently using matrix exponentiation.
Modular exponentiation: frequently asked questions
What is modular exponentiation?
Modular exponentiation computes a^b mod m, which is the remainder when a raised to the power b is divided by m. For example, 2^10 mod 1000 = 1024 mod 1000 = 24. The result always lies in the range 0 to m-1.
Why not just compute a^b and then take the modulo?
For large exponents, a^b becomes astronomically large and cannot be stored as a regular integer. The binary (fast) exponentiation method reduces intermediate values by taking the modulo at each squaring step, keeping numbers small throughout.
What is the binary exponentiation algorithm?
Write b in binary. Start with result = 1 and base = a mod m. For each bit of b from least significant to most significant: if the bit is 1, multiply result by base and take mod m; then square base and take mod m. This runs in O(log b) multiplications.
Where is modular exponentiation used?
RSA encryption: computing c = m^e mod n for encryption and m = c^d mod n for decryption. Diffie-Hellman key exchange: computing g^x mod p. Primality testing: Fermat's little theorem checks whether a^(p-1) mod p = 1.
What is a^0 mod m?
By convention, a^0 = 1 for any a, so a^0 mod m = 1 mod m = 1 for m > 1. When m = 1, the result is 0 because any integer mod 1 = 0.
Official sources
- NIST FIPS 186-5 (Digital Signature Standard): csrc.nist.gov.
- NIST SP 800-56A, Key Establishment Schemes: csrc.nist.gov.
Reviewed by the CalculatorHub team, edited by James Graham, 15 June 2026. See our methodology.