We’ve all done math problems that look like this: 35, 410, or N37. These are known as an exponentiation. And there is a trick to solving these problems with less calculations than simply multiplying the base number over and over again. That trick is known as the Square and Multiply method.
Take 35. If doing that one manually, without the Square and Multiply method, it would take 5 different calculations:
3 * 3 * 3 * 3 * 3
- Convert the exponent to Binary.
- For the first 1, simply list the number
- For each ensuing 0, do Square operation
- For each ensuing 1, do Square and Multiply operations
As an example, lets run 35 through the process:
5 = 101 in Binary 1 First One lists Number 3 0 Zero calls for Square (3)2 1 One calls for Square + Multiply ((3)2)2*3
Of course, going from five calculations to three calculations is not a huge gain in efficiency. But as you use the Square and Multiply method with bigger and bigger exponent values, the efficiency increase gets larger.
Take a look at what happens when you use an exponent of 37 (aka,
37 = 100101 in Binary 1 First One lists number N 0 Zero calls for Square (N)2 0 Zero calls for Square ((N)2)2 1 One calls for Square + Multiply (((N)2)2)2*N 0 Zero calls for Square ((((N)2)2)2*N)2 1 One calls for Square + Multiply (((((N)2)2)2*N)2)2*N
We went from requiring 37 steps to only 7.
You can determine the total number of calculations required when using the Square and Multiple method. Since each step requires at least a square operation, each binary digit (after the first) result in at least one operation. Then, since each binary 1 also calls for an additional and multiply operation, you count the binary 1’s a second time.
Or, to put it another way, ignoring the left-most binary 1, count each binary 0 as one operation, and each binary 1 as two operations.
Here are some more examples:
5 101 3 calculations 21 100101 7 calculations 47 101111 9 calculations 56 111000 7 calculations 99 1100011 9 calculations 112 1110000 8 calculations 1024 10000000000 10 calculations
A lot of Cryptography math formulas require exponentiation on incredibly large numbers. When doing such large calculations, computers use methods like the Square and Multiply method to achieve the end result without having to go through every multiplication operation a typical exponentiation would require.