Modular exponentiation

Modular exponentiation computes a^b mod n — the remainder of a^b divided by n — efficiently. It is the fundamental operation of essentially all modern public-key cryptosystems: RSA, Diffie-Hellman, ElGamal, elliptic curves over finite fields. Without a fast algorithm for it, asymmetric cryptography would be computationally impractical.

Naive a^b followed by "% n" is impossible for large exponents: 2^1024 has over 300 decimal digits. The solution is square-and-multiply (or binary exponentiation), reducing complexity from O(b) to O(log b) modular multiplications.

Square-and-multiply

Express exponent b in binary and read it left-to-right (or right-to-left), squaring the result at each bit and multiplying by a when the bit is 1. Formally, if b = ∑ b_i·2ⁱ:

a^b = a^b₀ · (a²)^b₁ · (a⁴)^b₂ · …

After each squaring and multiplication the result is reduced mod n, keeping intermediates below n². Total operations: at most 2·⌊log₂ b⌋. For b = 2^1024, about 2048 modular multiplications — a fraction of a second.

The four modes

1. Direct a^b mod n: full square-and-multiply trace.
2. Fermat test: verifies a^(n−1) ≡ 1 (mod n). By Fermat's little theorem any prime p satisfies this for all a coprime to p. An n failing it is definitely composite. Beware of Carmichael numbers (561, 1105, 1729, 2465, ...) which are composite yet pass the test for every coprime a.
3. Multiplicative order: smallest k > 0 with a^k ≡ 1 (mod n). By Lagrange's theorem in (ℤ/nℤ)* the order divides φ(n). If ord_n(a) = φ(n), a is a primitive root.
4. RSA demo: full encryption/decryption simulation with primes p, q, public e and message m. Computes n = pq, φ(n), d = e⁻¹ mod φ(n), then c = m^e mod n and verifies m' = c^d mod n.

Fermat's little theorem

If p is prime and gcd(a, p) = 1, then a^p−1 ≡ 1 (mod p)

Quick proof: in ℤ/pℤ the numbers 1, 2, …, p−1 form a multiplicative group of order p−1. By Lagrange, every element's order divides the group order, so a^(p−1) = 1. This gives a very fast probabilistic primality test — but not foolproof: Carmichael numbers (discovered 1910) are composite and pass Fermat for every coprime base. Alford-Granville-Pomerance (1994) proved there are infinitely many, but they are rare: the smallest is 561 and only 2163 exist below 10⁹.

The RSA algorithm

RSA (Rivest, Shamir, Adleman, 1977) is the most used public-key cryptosystem:

1. Key generation: pick large primes p, q (typically 1024 bits each). Compute n = p·q and φ(n) = (p−1)(q−1). Pick e coprime with φ(n) (often e = 65537). Compute d = e⁻¹ mod φ(n) via extended Euclidean.
2. Public key: (n, e). Private key: (n, d). Primes p, q destroyed after d.
3. Encryption: c = m^e mod n.
4. Decryption: m = c^d mod n.

Correctness uses Euler's theorem: m^(e·d) ≡ m (mod n) since e·d ≡ 1 (mod φ(n)). Security rests on the difficulty of factoring n: without p, q (hence φ(n)), deriving d from e needs sub-exponential work (current record is the general number-field sieve, GNFS). RSA-2048 is considered secure for decades.

Other systems using modpow

• Diffie-Hellman (1976): key agreement via discrete log. Alice/Bob agree on prime p and generator g, exchange g^a mod p and g^b mod p, compute shared g^(ab) mod p.
• ElGamal (1985): encryption using discrete log. Used in PGP and GPG signatures.
• DSA: digital signature standard based on discrete log in ℤ/pℤ.
• Elliptic curves (ECC): replaces a^b mod p with [k]P on elliptic curves, achieving equivalent security with 10× smaller keys. Used by Bitcoin (secp256k1), TLS 1.3, Signal.

Advanced optimisations

• Montgomery reduction: removes costly divisions via domain transformation.
• CRT (Chinese remainder theorem): RSA decryption works separately mod p and mod q, then combines — 4× faster than direct mod n.
• Sliding window: precomputes odd-exponent powers of a (a³, a⁵, …), reducing multiplications by ~20%.
• Barrett reduction: Montgomery alternative with different latency characteristics.

Updated July 2026