A fast way to do modular exponentiation

In number theory and in cryptography, it is often necessary to raise a number a to a number e modulo another number N (the number e 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 a to a number e modulo another number N is a^{e} \ (\text{mod} \ N). The answer to this exponentiation is in effect the remainder obtained by dividing the number a^e by N. For example the answer of 2^{6} \ (\text{mod} \ 11) is 9. When 2^6= 64 is divided by 11, the remainder is 9. We use the notation 2^{6} \equiv 9 \ (\text{mod} \ 11) to express this result. In cryptography, the exponent e and the modulo N are large numbers with hundreds or even thousands of decimal digits. For example, it can be verified that c^{d} \equiv m \ (\text{mod} \ N) where

    N=
    11438162575788886766923577997614661201021829672124
    23625625618429357069352457338978305971235639587050
    58989075147599290026879543541

    c=
    96869613754622061477140922254355882905759991124574
    31987469512093081629822514570835693147662288398962
    8013391990551829945157815154

    d=
    10669861436857802444286877132892015478070990663393
    78628012262244966310631259117744708733401685974623
    06553968544513277109053606095

    m=
    20080500130107090300231518041900011805001917210501
    1309190800151919090618010705

The modulus N 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 N into its prime factors. Knowing the prime factors of the modulus N means that any message encrypted using that modulus will no longer be secure. The 129-digit N 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 c^{d} \equiv m \ (\text{mod} \ N).

___________________________________________________________________________

Examples

Example 1
To illustrate how fast powering works, we start with a small example. We perform 3^{23} (\text{mod} \ 29). 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 3^{23} into a series of squarings and multiplications. To this end, we write 23 as a sum of powers of two as follows:

    23=2^0+2^1+2^2+2^{4}

Next we compute 3^{2^0},3^{2^1},3^{2^2},3^{2^3},3^{2^{4}} modulo 29. 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:

    \displaystyle \begin{aligned} &3^{2^0} \equiv 3 \ * \\&3^{2^1} \equiv 9 \ * \\&3^{2^2} \equiv 9^2 \equiv 23  \ * \\&3^{2^3} \equiv 23^2 \equiv 7 \\&2^{2^{4}} \equiv 7^2 \equiv 20 \ * \end{aligned}

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 29. The next step is to multiply the numbers with *. After each multiplication, reduce modulo 29.

    \displaystyle \begin{aligned} 3^{23} &\equiv 3 \cdot 9 \cdot 23 \cdot 20  \\&\equiv 27 \cdot 23 \cdot 20 \\&\equiv 12 \cdot 20 \\&\equiv 8 \ \text{mod} \ 29  \end{aligned}

Thus the answer is 3^{23} \equiv 8 \ (\text{mod} \ 29). 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

\left[\begin{array}{lllll}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 3* & \text{ } & 3 \\      1  & \text{ } & 9* & \text{ } & 27 \\      2  & \text{ } & 23* & \text{ } & 12 \\      3  & \text{ } & 7 & \text{ } & \text{ } \\      4  & \text{ } & 20* & \text{ } & 8          \end{array}\right]

Example 2
Verify the following

    30120^{17} \equiv 23877 \ (\text{mod} \ 44197)

    23877^{41201} \equiv 30120 \ (\text{mod} \ 44197)

This is a toy example of RSA encryption (the first calculation) and decryption (the second). The modulus N= 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.

    41201=2^0+2^4+2^5+2^{6}+2^{7}+2^{13}+2^{15}

The following table shows the squarings and multiplications.

Example 2 Results

\left[\begin{array}{lllll}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 23877* & \text{ } & 23877 \\      1  & \text{ } & 14026 & \text{ } & \text{ } \\      2  & \text{ } & 7829 & \text{ } & \text{ } \\      3  & \text{ } & 36199 & \text{ } & \text{ } \\      4  & \text{ } & 14945* & \text{ } & 39384 \\      5  & \text{ } & 25584* & \text{ } & 41247 \\      6  & \text{ } & 27683* & \text{ } & 11206 \\      7  & \text{ } & 16706* & \text{ } & 33141 \\      8  & \text{ } & 30578 & \text{ } & \text{ } \\      9  & \text{ } & 26549 & \text{ } & \text{ } \\      10  & \text{ } & 39842 & \text{ } & \text{ } \\      11  & \text{ } & 5512 & \text{ } & \text{ } \\      12  & \text{ } & 18805 & \text{ } & \text{ } \\      13  & \text{ } & 7828* & \text{ } & 35555 \\      14  & \text{ } & 20542 & \text{ } & \text{ } \\      15  & \text{ } & 25005* & \text{ } & 30120      \end{array}\right]

The modulus in this example is small enough so that all the reduction modulo N can be done by a hand-held calculator. For example, take the first squaring. The square 23877^2 divided by 44197 leads to the quotient 12899. Then 23877^2-12899 \cdot 44197 produces the remainder 14026. For a larger modulus N, 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

    230914^{17} \equiv 347965 \ (\text{mod} \ 497347)

    347965^{204209} \equiv 230914 \ (\text{mod} \ 497347)

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

    204209=2^0+2^4+2^5+2^{7}+2^{8}+2^{10}+2^{11}+2^{12}+2^{16}+2^{17}

The following table shows the squarings and multiplications.

Example 3 Results

\left[\begin{array}{lllll}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 347965* & \text{ } & 347965 \\      1  & \text{ } & 16728 & \text{ } & \text{ } \\      2  & \text{ } & 316970 & \text{ } & \text{ } \\      3  & \text{ } & 416083 & \text{ } & \text{ } \\      4  & \text{ } & 64230* & \text{ } & 12464 \\      5  & \text{ } & 496882* & \text{ } & 172404 \\      6  & \text{ } & 216225 & \text{ } & \text{ } \\      7  & \text{ } & 145890* & \text{ } & 187076 \\      8  & \text{ } & 424582* & \text{ } & 299597 \\      9  & \text{ } & 486410 & \text{ } & \text{ } \\      10  & \text{ } & 254689* & \text{ } & 88899 \\      11  & \text{ } & 4246* & \text{ } & 476128 \\      12  & \text{ } & 124024* & \text{ } & 295068 \\      13  & \text{ } & 4560 & \text{ } & \text{ } \\      14  & \text{ } & 402373 & \text{ } & \text{ } \\      15  & \text{ } & 175484 & \text{ } & \text{ } \\      16  & \text{ } & 400057* & \text{ } & 200467 \\      17  & \text{ } & 333343* & \text{ } & 230914 \\    \end{array}\right]

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 a^{e} \ (\text{mod} \ N). They are:

  1. Find the binary expansion of the exponent e.
  2. Perform the series of squarings a^{2^0}, a^{2^1}, a^{2^2}, \cdots up to the highest power of 2 in the binary expansion of the exponent. The result of each squaring is immediately reduced modulo N.
  3. Multiply the results of the squarings that correspond to the powers of 2 in the binary expansion of the exponent e. The result of each multiplication is immediately reduced modulo N. 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 k is the highest power of 2 in the exponent E in the exponentiation a^{E} \ (\text{mod} \ N). So we have:

    \displaystyle 2^k \le E \le 2^{k+1}-1

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

    \displaystyle k \le \frac{\text{log}(E)}{\text{log}(2)}

    \displaystyle 2k \le 2 \ \frac{\text{log}(E)}{\text{log}(2)}

This means that the algorithm takes at most \displaystyle 2 \ \frac{\text{log}(E)}{\text{log}(2)} multiplications. In particular, if E is roughly 2^n in size, then the fast powering algorithm requires at most \displaystyle 2 \ \frac{\text{log}(2^{n})}{\text{log}(2)}=2n multiplications. For example, the exponent in Example 4 is roughly 2^{129} in size. Thus the fast powering algorithm will take at most 258 multiplications for that example. Another example is when the exponent E is a 1024-bit number (309 decimal digits) and is thus roughly 2^{1024}. 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).

___________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Advertisements

3 thoughts on “A fast way to do modular exponentiation

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

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

  3. Pingback: Fermat numbers | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s