Modular Exponentiation

Modular exponentiation and binary squaring

Modular exponentiation computes a^b mod n without ever building the gigantic intermediate a^b. The standard method is exponentiation by squaring (also called binary exponentiation): write b in binary, square the running value at each bit, and multiply by a whenever the bit is 1 — reducing modulo n after every step. Complexity is O(log b) multiplications instead of O(b). Example: 3^200 mod 50. Successive modular squares: 3^2 = 9, 3^4 = 81 mod 50 = 31, 3^8 = 31^2 mod 50 = 961 mod 50 = 11, and so on — the working number never exceeds n^2. Fermat's little theorem provides a check: a^(p−1) ≡ 1 (mod p) when p is prime and gcd(a, p) = 1.

Cryptographic and computational uses

• RSA — both encryption and signing are c = m^e mod n, typically with e = 65537 = 2^16 + 1.
• Diffie–Hellman key exchange relies on g^x mod p being cheap to compute and the inverse (discrete log) being hard.
• Digital signatures — DSA and ECDSA chain modular exponentiation over integer and elliptic-curve groups.
• Primality tests — Miller–Rabin and Fermat tests use modular exponentiation as their core operation.

FAQ

Why not just compute a^b first and then take mod? Because a^b can have billions of digits. Reducing modulo n after every squaring keeps numbers below n^2.

Is the result the same regardless of when you take mod? Yes — modular arithmetic is compatible with multiplication: (x · y) mod n = ((x mod n) · (y mod n)) mod n.

What about negative exponents? a^(−k) mod n means (a^(−1))^k mod n, requiring the modular inverse of a — which exists only when gcd(a, n) = 1.

How many multiplications for a 2048-bit exponent? Around 2048 squarings plus an average of 1024 conditional multiplications — about 3000 operations, finishing in milliseconds.