In number theory and in cryptography, it is often necessary to raise a number to a number modulo another number (the number here stands for exponent and is not to be confused with the natural log constant). In this post we explain an algorithm that can do such exponentiation efficiently. This algorithm goes by many names. Some of the common ones are fast powering algorithm, fast modular exponentiation, and square and multiply.

The next post shows how the fast powering algorithm is used in the context of primality testing (i.e. checking whether or not a number is prime).

The usual notation for raising a number to a number modulo another number is . The answer to this exponentiation is in effect the remainder obtained by dividing the number by . For example the answer of is 9. When 64 is divided by 11, the remainder is 9. We use the notation to express this result. In cryptography, the exponent and the modulo are large numbers with hundreds or even thousands of decimal digits. For example, it can be verified that where

11438162575788886766923577997614661201021829672124

23625625618429357069352457338978305971235639587050

58989075147599290026879543541

96869613754622061477140922254355882905759991124574

31987469512093081629822514570835693147662288398962

8013391990551829945157815154

10669861436857802444286877132892015478070990663393

78628012262244966310631259117744708733401685974623

06553968544513277109053606095

20080500130107090300231518041900011805001917210501

1309190800151919090618010705

The modulus is a 129-digit number that is used as the modulus of a factoring challenge problem called RSA-129 challenge. The challenge was to factor the number into its prime factors. Knowing the prime factors of the modulus means that any message encrypted using that modulus will no longer be secure. The 129-digit was factored in 1994. So the RSA encryption scheme using any modulus similarly in size is not secure. So the calculation as shown above is actually considered a toy problem, though a more realistic one. The fast powering algorithm (or square-and-multiply algorithm) discussed here can be used to calculate .

___________________________________________________________________________

**Examples**

*Example 1*

To illustrate how fast powering works, we start with a small example. We perform . In the fast powering approach, we do not need to raise 3 to 23. Instead, we first find the binary expansion of the exponent 23 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”. The following shows the squarings, all modulo 29:

Note that the squarings marked by * are the powers of 2 in the binary expansion of 23. In the above series of squarings, there are 4 multiplications and 4 divisions for the reduction modulo . The next step is to multiply the numbers with *. After each multiplication, reduce modulo 29.

Thus the answer is . To simplify the presentation of the calculation, we use a table such as the one below. The middle column shows the squarings. The asterisks in the squaring column indicate that the results come from the powers of 2 in the binary expansion of the exponent, meaning that these will be the numbers to be multiplied in the third column.

**Example 1 Results**

*Example 2*

Verify the following

This is a toy example of RSA encryption (the first calculation) and decryption (the second). The modulus 44197 and the first exponent 17 are the public key. The first exponentiation turns the message 30120 into the ciphertext 23877. The second exponentiation converts the ciphertext back into the original message. We demonstrate how to do the decryption (the second calculation). First express the exponent 41201 into its binary expansion.

The following table shows the squarings and multiplications.

**Example 2 Results**

The modulus in this example is small enough so that all the reduction modulo can be done by a hand-held calculator. For example, take the first squaring. The square divided by 44197 leads to the quotient 12899. Then produces the remainder 14026. For a larger modulus , use a calculator or software that can handle multiplication and divisions of larger numbers.

*Example 3*

This is a slightly larger example that is similar to Example 2. Verify the following

We perform the second exponentiation. The following is the binary expansion of the exponent 204209.

The following table shows the squarings and multiplications.

**Example 3 Results**

*Example 4*

This is the RSA-129 challenge problem mentioned earlier. We do not perform the calculation here. The discussion in the running time section below shows that this example requires at most 258 multiplications even though this example is so much larger than the other three examples. The RSA-129 challenge problem is also discussed in another blog authored by the author of this blog.

___________________________________________________________________________

**Steps in the algorithm**

To summarize, there are three steps in carry out the fast exponentiation for . They are:

- Find the binary expansion of the exponent .
- Perform the series of squarings up to the highest power of 2 in the binary expansion of the exponent. The result of each squaring is immediately reduced modulo .
- Multiply the results of the squarings that correspond to the powers of 2 in the binary expansion of the exponent . The result of each multiplication is immediately reduced modulo . The last multiplication result is the answer to the modular exponentiation.

Note that the squarings in the second step are shown in the second column in the above tables. The multiplications are performed in the third column but only for the rows that are the powers of 2 in the binary expansion of the exponent (the rows with *).

___________________________________________________________________________

**Running time**

Let’s look at the running time of the fast powering algorithm. Suppose that is the highest power of 2 in the exponent in the exponentiation . So we have:

The above inequality means that the exponent is a -bit number. The above three examples demonstrate that the squaring step requires exactly multiplications and that the multiply step requires at most multiplications. Overall, the algorithm requires at most many multiplications and the same number of divisions to reduce modulo . Since , by taking natural log of both sides we have:

This means that the algorithm takes at most multiplications. In particular, if is roughly in size, then the fast powering algorithm requires at most multiplications. For example, the exponent in Example 4 is roughly in size. Thus the fast powering algorithm will take at most 258 multiplications for that example. Another example is when the exponent is a 1024-bit number (309 decimal digits) and is thus roughly . Then the algorithm requires at most 2048 multiplications. Thus the fast powering algorithm is fast and efficient.

The next post shows how the fast powering algorithm is used in the context of primality testing (i.e. checking whether or not a number is prime).

___________________________________________________________________________

Pingback: An easy method for detecting composite numbers | All Math Considered

Pingback: Fermat’s Little Theorem as a primality testing | All Math Considered

Pingback: Fermat numbers | Exploring Number Theory