Algorithms for repeated squaring

An algorithm for a computational problem is a computational method, a procedure, that takes in the inputs and spits out an output that obeys the mathematical relation defined in the computational problem.

We've learned two algorithms for the modular exponentiation problem, one we call the naive algorithm and one we call the repeated squaring algorithm. The naive algorithm simply starts with b and multiplies by b over and over, calculating the result mod m each time. After k-1 multiplications, the result is .

The repeated squaring algorithm consists of two parts. In the first part, the algorithm starts with b, then multiplies it by itself (``squares'' it) mod m, then squares the result mod m, and then squares that mod m, etc. In the second part, the algorithm combines together some of these results, multiplying them together mod m. In order to make the algorithm more precise, we need the notion of binary expansion.

We ordinarily write numbers in base 10 (``decimal'') notation. The rightmost digit is in the ones place, the second-to-rightmost digit is in the tens place, the third-to-rightmost digit is in the hundreds place, and so on. Thus 765 represents 7 times plus 6 times plus 5 times .

Another system for writing numbers is base 2 (``binary''), where the rightmost digit is in the ones place, the second-to-rightmost digit is in the twos place, the third-to-rightmost digit is in the fours place, the fourth-to-rightmost digit is in the eights place, and so on. Thus 100111 represents 1 times plus 0 times plus 0 times plus 1 times plus 1 times plus 1 times , which is 39. The digits in binary notation are called ``bits'' (short for ``binary digits''). By convention, the leftmost bit must be a 1 (just as ordinarily we don't write the number 7 as 007).

Back to the repeated-squaring algorithm. To calculate , we write k in binary. The position of the leftmost bit tells us how many squarings need to take place in the first part of the algorithm. For example, if the leftmost bit is in the s place, then we need to calculate . Since the first number is just b, we need 11 squarings.

The ones in the binary representation of k tell us which powers of b that we have calculated we need to combine to get the final result. Here is an example, the multiplications needed to calculate . Next to each multiplication row, I have indicated an expression for the value calculated in that row.

NAME COMMAND value

result0 b result1 result2 result3 result4 result5 result6 result7 result8 result9 result10 result11 finalresult

Say the exponent k takes L bits to represent. Then the number of multiplications for the first part of the algorithm is L-1. In the second part of the algorithm, we need to multiply together some of the L results we obtained in the first part. Since we need to multiply together at most L values, we need at most L-1 multiplications in the second part of the algorithm.

The number of bits needed to represent a positive integer k is 1 plus the rounded-down value of , (the base-2 logarithm of k). For example, , so the rounded-down value of the logarithm is 11. Thus this formula predicts that the number of bits needed to represent 2184 is 12. (For most purposes, it is good enough to neglect the ``1 plus'' and estimate the number of bits by .)

Similarly, the number of decimal digits needed to represent a number, say m, is 1 plus the rounded down value of the base-10 logarithm. for example, is 2.8836614..., so the rounded-down value is 2. Thus this formula predicts that the number of decimal digits to represent 765 is 3.

It is easy to convert between the base-10 log of a number and its base-2 log using the following formula. Memorize it!

(The symbol denotes ``is approximately equal to''. For those who are curious about where the 3.3 comes from, this is the base-2 logarithm of 10.)