In some cryptography applications such as RSA algorithm, it is necessary to compute modulo where the power and the modulus are very large numbers. We discuss and demonstrate an efficient algorithm that can handle such calculations. This general algorithm has various names such as fast powering algorithm, square-and-multiply algorithm and exponentiation by squaring.
The problem at hand is to compute . The naïve approach is to compute by repeatedly multiplying by and reducing modulo . When the power is large (e.g. an integer with hundreds of digits), this approach is difficult or even impossible (given the current technology). In this post we discuss an alternative that is known as the fast powering algorithm.
Compute modulo .
Using the naïve approach described earlier, we would do something like the following:
In this naïve approach, we would multiply two numbers at a time and then reduce the result modulo so that the numbers do not get too large. The above example would involve multiplications and then divisions for the reduction modulo . Great difficulty comes when the power is not and instead is an integer with hundreds or even thousands of digits.
Note that in the above naïve approach, the power is reduced by one at each step. In the fast power alternative, the power comes down by an exponent of two in each step. The idea is to use the binary expansions of the exponent to transform the computation of into a series of squarings and multiplications. To this end, we write as a sum of powers of two as follows:
Next we compute modulo . Note that each term is the square of the preceding term, hence the word square in the name “square-and-multiply”. To make it easier to see, we put the results in the following table.
Note that the rows marked by * in the above table are the results that we need. In the above table, there are 10 multiplications for the squarings and 10 divisions for the reduction modulo .
Now is calculated as follows:
We have the answer . The calculation in (3) is the step that gives the word “multiply” in the name “square-and-multiply”. In this step, we multiply the results obtained from the previous step.
We now tally up the amount of work that is done. The calculation in table (2) requires 10 multiplications for the squaring and 10 divisions for the reduction modulo . The calculation in (3) requires 4 multiplications and 4 divisions for the reduction modulo . Together, there are 14 multiplications and 14 divisions. In contrast, the naïve approach would require 1170 multiplications and 1170 divisions!
Description of Fast Powering Algorithm
To compute , use the following steps. The following steps correspond with the steps in the above example.
Compute the binary expansions of the power .
where each , or . In particular, we assume that .
For each , compute modulo . Note that each is the result of squaring the previous term . We arrange the calculation in the following table.
Compute using the following derivation.
The last line in (3) is to be further reduced modulo . In the actual calculation, only the terms with need to be used.
We now establish an upper bound for the number multiplications. Step (2) requires multiplications and divisions to reduce modulo . Step (3) requires at most many multiplications since some of the many be zero. Step (3) also requires at most many divisions to reduce modulo . So altogether, the algorithm requires at most multiplications and divisions.
From Step (1), we know that . Take natural log of both sides, we have and . So the fast powering algorithm requires at most
many multiplications and at most that many divisions to compute the congruence calculation .
For example, when the power , which is a Mersenne prime, which has 39 digits. Now . By the above calculation, the fast powering algorithm would take at most 254 multiplications and at most 254 divisions to do the power congruence computation.
The fast powering calculations demonstrated in this post can be done by hand (using a hand-held calculator). In real applications, such calculations should of course be done in a computer.
Use the fast power algorithm to show that
Note that one congruence is encryption and the other one is decryption. We demonstrate the second calculation.
In doing the second calculation, we use a little bit of help from Fermat’s little theorem. The modulus is a prime number. So . Thus we have:
The binary expansions of are:
Compute modulo for each . The computation is displayed in the following table. The rows with * are the results that we need for Step (3).