The problem
Many tasks need the value of a base raised to an exponent, all taken modulo some number. The exponent can be enormous, so multiplying the base by itself that many times is hopeless. Modular exponentiation computes the answer with a number of multiplications proportional to the number of bits in the exponent.
The trick: square and multiply
The idea rests on two facts:
- Squaring the base doubles the exponent. So from the base you can reach the second power, the fourth power, the eighth power, and so on by repeated squaring.
- Any exponent can be written in binary, as a sum of these powers of two.
You walk the exponent's bits from low to high. At each step you square a running base. Whenever the current bit is set, you multiply the running base into the answer. Every multiplication is reduced modulo the divisor immediately, so the numbers never grow large.
Why it is fast
A million bit exponent needs only about a million multiplications, not an astronomical count. This makes it the backbone of cryptography and number theory.
Key idea
Express the exponent in binary and combine repeated squaring with selective multiplies, reducing modulo at every step so values stay small.