What is modular exponentiation?
Modular exponentiation computes \(a^b \bmod m\) — the remainder left when the power \(a^b\) is divided by the modulus m. It is one of the most important operations in number theory and cryptography, powering algorithms such as RSA, Diffie–Hellman key exchange and digital signatures. Even when \(a^b\) is astronomically large, the result modulo m stays small and computable.
How to use this calculator
Enter three whole numbers: the base a, the non-negative exponent b, and the modulus m (a positive integer). Click calculate and you will get the single remainder in the range 0 to m−1. The base may be negative; it is first normalized into the valid residue range before exponentiation.
The formula explained
Computing \(a^b\) directly is impossible for large b, so this tool uses the square-and-multiply method (also called fast or binary exponentiation). The formula is:
$$\text{result} = \text{Base } a^{\text{Exponent } b} \bmod \text{Modulus } m$$The exponent is read in binary. Starting with result \(r = 1\) and base b reduced mod m, for each bit of the exponent the base is squared (mod m); whenever the current bit is 1, the result is multiplied by the base (mod m). This needs only about \(\log_2(b)\) multiplications instead of b of them.
Worked example
Compute \(4^{13} \bmod 497\). The exponent 13 in binary is 1101. Walking through square-and-multiply:
$$4^1 = 4,\quad 4^2 = 16,\quad 4^4 = 256,\quad 4^8 = 256^2 = 65536 \equiv 30 \pmod{497}$$Since \(13 = 8 + 4 + 1\), multiply the matching powers:
$$30 \times 256 \times 4 = 30720 \equiv 445 \pmod{497}$$So \(4^{13} \bmod 497 = \textbf{445}\).
FAQ
What if the exponent is 0? Any number to the power 0 is 1, so the result is \(1 \bmod m\) (which is 0 when \(m = 1\)).
Can the base be negative? Yes. A negative base is converted to its equivalent positive residue mod m first, so the answer is always between 0 and m−1.
Why not just compute \(a^b\) then take mod? For cryptographic sizes \(a^b\) would have millions of digits. Reducing mod m at every step keeps the numbers small and the computation fast.
