Binary Exponentiation: The Same Algorithm in a Modern Textbook
Chapter Twenty-One
Syllabus topic Module 1, "Algorithmic generation", "Complexity & Limitations"
Pages 67 to 69 of 378
In one line
Binary exponentiation computes a power by squaring and multiplying instead of by multiplying over and over, and it turns n multiplications into about log n.
In the wording you can write in an examination: binary exponentiation, also called exponentiation by squaring or the square-and-multiply method, computes a to the power n by writing n in binary and processing its bits, squaring the running result at each bit and multiplying by a where the bit is one. It performs at most 2 log n multiplications instead of n minus 1.
The problem, and the naive cost
To compute a to the power n, the obvious method multiplies a by itself n minus 1 times. For n equal to 1000 that is 999 multiplications.
Squaring changes the arithmetic of the situation. If you know a to the power 500, then one squaring gives a to the power 1000. If you know a to the power 500, one more multiplication by a gives a to the power 501. So each step either doubles the exponent or adds one to it, and you can reach any exponent by a sequence of doublings and single additions.
That is exactly Piṅgala's saṅkhyā rule with the base left free instead of fixed at two.
The method, from the top down
Write n in binary. For n equal to 13 that is 1101.
Read the bits from the most significant end. Start with the result equal to a.
For each remaining bit: square the result; and if the bit is one, multiply by a as well.
Trace it for a to the power 13. Bits after the first: 1, 0, 1.
| Step | Bit | Operation | Exponent reached |
|---|---|---|---|
| start | 1 | result is a | 1 |
| 1 | 1 | square, then multiply by a | 3 |
| 2 | 0 | square | 6 |
| 3 | 1 | square, then multiply by a | 13 |
Five multiplications instead of twelve, and the pattern of the exponents, 1, 3, 6, 13, is the binary number being built one bit at a time.
The method, from the bottom up
There is a second formulation which is the one usually coded, because it needs no bit counting in advance.
FUNCTION power(a, n)
result <- 1
base <- a
while n > 0 do
if n is odd then result <- result * base
base <- base * base
n <- n / 2, discarding the remainder
end while
return result
It is the same algorithm read from the low-order end. The n / 2 is Piṅgala's halving; the "if n is odd" is his rūpe śūnyam.
The cost
Let b be the number of bits in n, which is about log n to base two, rounded up.
The top-down form does b minus 1 squarings and at most b minus 1 multiplications, so at most 2 log n multiplications in all.
Binary Exponentiation: The Same Algorithm in a Modern Textbook
Worked. For n equal to 1000, b is 10. So at most 18 multiplications against 999. For n equal to a million, b is 20, so at most 38 against nearly a million.
And the lower bound. You cannot do better than about log n, because each multiplication at best doubles the largest exponent you hold, so after k multiplications the highest exponent reachable is 2 to the power k.
Piṅgala's version against the general one
| Piṅgala's saṅkhyā | Binary exponentiation | |
|---|---|---|
| The base | fixed at two | any a |
| What is computed | the number of metrical patterns | a to the power n |
| The descent | halve, or take one off if odd | the same |
| The ascent | square at a halving, double at a subtraction | square at a halving, multiply by a at a subtraction |
| Cost | about log n operations | about log n operations |
| Stated as an economy | no | yes, that is the whole point of it |
The only mathematical difference is the fixed base. The doubling in his ascent is multiplication by the base, and his base happens to be two.
Why it still matters: modular exponentiation
This is the sentence to remember, because it links Module I to Module II.
Public-key cryptography rests on computing a to the power e modulo m where e and m are hundreds of digits long. With repeated multiplication that is impossible: there is not enough time in the universe. With square and multiply it is a few thousand multiplications, each of them on numbers of a few hundred digits, which is a fraction of a second.
Two details make it practical, and both are worth naming.
Reduce modulo m at every step. Otherwise the intermediate numbers grow to astronomical size. Squaring a number of d digits gives 2d digits, so after twenty squarings you would have a million digits.
The bits of the exponent are secret. Because the algorithm does an extra multiplication exactly when a bit is one, an attacker who can measure the time or the power consumption can read the exponent off. Real implementations therefore do the same work whichever the bit is. That is a whole field, and [Symmetric Encryption] and [Cipher Algorithms, Classical to Modern] return to the general point that an algorithm's timing can leak its secrets.
What it does NOT mean
It does not mean Piṅgala invented the algorithm for a general base. His base is two throughout and no generalisation appears.
It does not mean the method is always best. For a small n, repeated multiplication is simpler and the difference is nothing. The method earns its keep when n is large.
Binary Exponentiation: The Same Algorithm in a Modern Textbook
It does not mean the cost is exactly log n. It is between log n and 2 log n depending on how many ones the exponent has, and an answer that says "about log n" is right while one that says "log n" is imprecise.
Quick revision
- Binary exponentiation: square at each bit, multiply by the base where the bit is one. At most 2 log n multiplications.
- Top down, from the most significant bit: result starts at a, then square and conditionally multiply.
- Bottom up: while n is positive, multiply into the result if n is odd, square the base, halve n.
- Piṅgala's saṅkhyā is the same algorithm with the base fixed at two, and his doubling is multiplication by that base.
- The lower bound is about log n, because each multiplication at best doubles the largest exponent held.
- It is what makes public-key cryptography possible; reduce modulo m at every step, and beware that the timing leaks the exponent.
Test yourself
1. Compute a to the power 13 by squaring, listing the exponents reached.
Write 13 as 1101. Start at a, exponent 1. Square and multiply by a: 3. Square: 6. Square and multiply by a: 13. Five multiplications.
2. Give the cost of the method and the reason it cannot be improved much.
At most 2 log n multiplications, since there are about log n bits and each contributes a squaring and possibly one multiplication. It cannot be improved beyond about log n because each multiplication at best doubles the largest exponent held, so k multiplications reach at most 2 to the power k.
3. What is the one mathematical difference between Piṅgala's saṅkhyā and binary exponentiation?
Piṅgala's base is fixed at two, so his "multiply by the base" step appears as doubling. Otherwise the descent and the ascent are identical.
4. Why must a modular exponentiation reduce at every step, and what does the algorithm leak if written naively?
Without reducing, the intermediate values double in length at each squaring and become unmanageable. Written naively it performs an extra multiplication exactly when an exponent bit is one, so its running time or power draw reveals the exponent.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.