fast modular exponentiation

Suppose you must compute something like 7^45 mod 13. Multiplying 7 by itself 45 times, reducing mod 13 as you go, works but is slow — and for cryptographic sizes the exponent has hundreds of digits, so a multiply-one-at-a-time loop would never finish. Fast modular exponentiation computes a^e mod m using only about log2(e) multiplications instead of e of them, by a trick called repeated squaring. It is the engine that makes RSA, Diffie-Hellman, and Miller-Rabin actually run.

The idea is to read the exponent in binary and build up the answer by squaring. Note that a^(2k) = (a^k)^2 and a^(2k+1) = a * (a^k)^2. So you can compute a^e by scanning the bits of e: maintain a running base that you square at every step (giving a^1, a^2, a^4, a^8, ...), and multiply the result by the current base exactly when that bit of e is 1. Crucially, you reduce mod m after every multiplication and every squaring, so the numbers never grow beyond about m^2 and stay small. A trace for 7^13 mod 11, with 13 = 1101 in binary: start result = 1, base = 7. Bit 1 (the 1s place): result = 7, base = 49 mod 11 = 5. Bit 0: result stays 7, base = 25 mod 11 = 3. Bit 1: result = 7*3 = 21 mod 11 = 10, base = 9. Bit 1: result = 10*9 = 90 mod 11 = 2. So 7^13 mod 11 = 2, in just 4 rounds rather than 13 multiplications.

The payoff is enormous: the running time is O(log e) modular multiplications, turning an exponent with hundreds of bits from astronomically many operations into a few hundred. This is what makes public-key cryptography practical — you can raise a 2048-bit number to a 2048-bit power with only a couple thousand multiplications. Two honest points: each multiplication of m-sized numbers itself costs O((log m)^2) with schoolbook arithmetic (or less with fast multiplication), so the total bit-cost includes that factor; and a careless implementation that skips the mod after each step lets the intermediate values explode to astronomical size, defeating the whole purpose.