We’ve all done math problems that look like this: 3^{5}, 4^{10}, or N^{37}. 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 3^{5}. 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 3^{5} through the process:

5 =101in Binary1FirstOnelists Number30Zerocalls for Square(3)^{2}1Onecalls 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, `N`

):^{37}

37 =100101in Binary1FirstOnelists numberN0Zerocalls for Square(N)^{2}0Zerocalls for Square((N)^{2})^{2}1Onecalls for Square + Multiply(((N)^{2})^{2})^{2}*N0Zerocalls for Square((((N)^{2})^{2})^{2}*N)^{2}1Onecalls 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:

51013 calculations 211001017 calculations 471011119 calculations 561110007 calculations 9911000119 calculations 11211100008 calculations 10241000000000010 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.

-2a square multiply a square

Nicely explained.

Thank you.