Powers without the long loop
Computing a raised to the n by multiplying a by itself n times is wasteful for large n. Fast exponentiation, also called exponentiation by squaring, reaches the answer in a number of multiplications that grows only with the number of bits in n.
The squaring trick
The exponent can be split using its binary form. Each squaring of the base covers one bit position:
- Keep a running result, starting at one.
- Look at the exponent bit by bit. Square the base at every step.
- Whenever the current bit is one, multiply the base into the result.
- Halve the exponent and repeat until it reaches zero.
Because the exponent halves each round, the loop runs about as many times as there are binary digits, not as many times as the exponent's value.
Where it shines
This is the workhorse of modular exponentiation: reduce modulo m after each multiplication and you can raise huge numbers to huge powers, exactly what RSA and Diffie Hellman demand. The same idea applies to matrix powers, used in fast Fibonacci computation.
Key idea
Exponentiation by squaring uses the binary form of the exponent: square the base each step and multiply it in when the bit is set, finishing in steps proportional to the bit length.