Modular Exponentiation

RSA is built on modular arithmetic. Computing a^b mod n for large numbers is the core operation.

Naive: compute a^b (a HUGE number), then take mod. For RSA-2048, this number has thousands of digits and overflows everything.

Square-and-multiply computes a^b mod n efficiently:

result = 1
base = a mod n
while b > 0:
    if b is odd:
        result = (result * base) mod n
    base = (base * base) mod n
    b = b >> 1
return result

Time: O(log b) multiplications, each mod n. For 2048-bit numbers: ~3000 multiplications. Fast.

Example: 7^560 mod 561:

b=560 (binary 1000110000)
Process bits right-to-left, squaring base:
b=0: skip; base² mod 561
b=0: skip; base² mod 561
... 4 zeros total ...
b=1 (bit 4): result *= base; base²
b=1 (bit 5): result *= base; base²
b=0: skip
b=0: skip
b=0: skip
b=1 (bit 9): result *= base

This is what pow(a, b, n) does in Python. Most languages have built-in modular exponentiation.

For larger gains: Montgomery multiplication, Barrett reduction. Used in production crypto libraries.