1.26: Computation of aN mod m

Let’s first consider the question: What is the smallest number of multiplications required to compute \(a^N\) where \(N\) is any positive integer?

Suppose we want to calculate \(2^8\). One way is to perform the following \(7\) multiplications: \[\begin{aligned} 2^2 &=2\cdot 2=4 \\ 2^3 &=2\cdot 4=8 \\ 2^4 &=2\cdot 8=16 \\ 2^5 &=2\cdot 16=32 \\ 2^6 &=2\cdot 32=64 \\ 2^7 &=2\cdot 64=128 \\ 2^8 &=2\cdot 128=256\end{aligned}\] But we can do it in only \(3\) multiplications: \[\begin{aligned} 2^2 &=2\cdot 2=4 \\ 2^4 &=\left(2^2\right)^2=4\cdot 4=16 \\ 2^8 &=\left(2^4\right)^2=16\cdot 16=256\end{aligned}\] In general, using the method: \[a^2=a\cdot a,a^3=a^2\cdot a,a^4=a^3\cdot a,\dotsc,a^n=a^{n-1}\cdot a\nonumber \] requires \(n-1\) multiplications to compute \(a^n\).

On the other hand if \(n=2^k\) then we can compute \(a^n\) by successive squaring with only \(k\) multiplications: \[\begin{aligned} a^2 &=a\cdot a \\ a^{2^2} &=\left(a^2\right)^2=a^2\cdot a^2 \\ a^{2^3} &=\left(a^{2^2}\right)^2=a^{2^2}\cdot a^{2^2} \\ \vdots \quad & \qquad \vdots \\ a^{2^k} &=\left(a^{2^{k-1}}\right)^2=a^{2^{k-1}}\cdot a^{2^{k-1}}\end{aligned}\] Note that the fact that \[2^k=\left(2^{k-1}\right)2=2^{k-1}+2^{k-1}\nonumber \] together with the Laws of Exponents: \[\left(a^n\right)^m=a^{nm}\nonumber \] and \[a^n\cdot a^m=a^{n+m}\nonumber \] is what makes this method work. Note that if \(n=2^k\) then \(k\) is generally a lot smaller than \(n-1\). For example, \[1024=2^{10}\nonumber \] and \(10\) is quite a bit smaller than \(1023\).

If \(n\) is not a power of \(2\) we can use the following method to compute \(a^n\).

The Binary Method for Exponentiation

Let \(n\) be a positive integer. Let \(x\) be any real number. This is a method for computing \(x^n\).

Step 27.1. Find the binary representation \[n=\left[a_r,a_{r-1},\dotsc,a_0\right]_2\nonumber \] for \(n\).

Step 27.2. Compute the powers \[x^2,x^{2^2},x^{2^3},\dotsc,x^{2^r}\nonumber \] by successive squaring as shown above.

Step 27.3. Compute the product \[x^n=x^{a_r2^r}\cdot x^{a_{r-1}2^{r-1}}\dotsm x^{a_12}\cdot x^{a_0}.\nonumber \]

Note \(\PageIndex{1}\)

Note each \(a_i\) is \(0\) or \(1\), so all needed factors were obtained in Step 2.

Example \(\PageIndex{1}\)

Let’s compute \(3^{15}\). Note that \(15=2^3+2^2+2+1=[1,1,1,1]_2\). So this takes care of Step \(1\). For Step \(2\), we note that \[\begin{aligned} 3^2 &=3\cdot 3=9 \\ 3^{2^2} &=9\cdot 9=81 \\ 3^{2^3} &=81\cdot 81=6561\end{aligned}\] So \(3^{15}=3^{2^3}\cdot 3^{2^2}\cdot 3^2\cdot 3^1\). For this we need \(3\) multiplications: \[\begin{gathered} 3\cdot 3^2=3\cdot 9=27 \\ \left(3\cdot 3^2\right)\cdot 3^{2^2}=27\cdot 81=2187 \\ \left(3\cdot 3^2\cdot 3^{2^2}\right) 3^{2^3}=2187\cdot 6561=14348907 \label{computation}\end{gathered}\] So we have \[3^{15}=14348907.\nonumber \] Note that we have used just \(6\) multiplications, which is less than the \(14\) it would take if we used the naive method. Let’s not forget that some additional effort was needed to compute the binary representation of \(15\), but not much.

Theorem \(\PageIndex{1}\)

Computing \(x^n\) using the binary method requires \(\lfloor\log_2(n)\rfloor\) applications of the Division Algorithm and at most \(2\lfloor\log_2(n)\rfloor\) multiplications.

Proof

If \(n=\left[a_r,\dotsc,a_0\right]_2\), \(a_r=1\), then \(n=2^r+\dotsb+a_12+a_0\). Hence \[\label{eq:1} 2^r\le n\le 2^r+2^{r-1}+\dotsb+2+1=2^{r-1}-1<2^{r+1}. \] Since \(\log_2\left(2^x\right)=x\) and when \(0<a<b\) we have \(\log_2(a)<\log_2(b)\), we have from \(\eqref{eq:1}\) that \[\log_2\left(2^r\right)\le\log_2(n)<\log_2\left(2^{r+1}\right)\nonumber \] or \[r\le\log_2(n)<r+1.\nonumber \] Hence \(r=\lfloor\log_2(n)\rfloor\). Note that \(r\) is the number of times we need to apply the Division Algorithm to obtain the binary representation \(n=\left[a_r,\dotsc,a_0\right]_2\), \(a_r=1\). To compute the powers \(x,x^2,x^{2^2},\dotsc,x^{2^r}\) by successive squaring requires \(r=\lfloor\log_2(n)\rfloor\) multiplications and similarly to compute the product \[x^{2^r}\cdot x^{a_{r-1}2^{r-1}}\dotsm x^{a_12}\cdot x^{a_0}\nonumber \] requires \(r\) multiplicatons. So after obtaining the binary representation we need at most \(2r=2\lfloor\log_2(n)\rfloor\) multiplications.

Use of a Calculator to Compute \(\log_2(x)\):

To find \(\log_2(x)\) one may use the formula \[\log_2(x)=\frac1{\ln(2)}\,\ln(x)\nonumber \] or \[\log_2(x)\approx\left[\frac1{(0.69314718)}\right]\,\ln(x)\nonumber \] where \(\ln(x)\) is the natural logarithm of \(x\). For small values of \(x\) it is sometimes faster to use the fact that \(r=\lfloor\log_2(x)\rfloor\) is equivalent to \[2^r\le x<2^{r+1},\nonumber \] that is, \(r\) is the largest positive integer such that \(2^r\le x\). The Maple command for \(\log_2(x)\) is log[2](x).

Note that if we count an application of the Division Algorithm and a multiplication as the same, the above tells us that we need at most \(3\lfloor\log_2(n)\rfloor\) operations to compute \(x^n\). So, for example, if \(n=10^6\), then it is easy to see that \(3\lfloor\log_2(n)\rfloor=57\). So we may compute \(x^{1,000,000}\) with only \(57\) operations.

Exercise \(\PageIndex{1}\)

Calculate \(3\lfloor\log_2(n)\rfloor\) for \(n=2,000,000\).

Exercise \(\PageIndex{2}\)

Use the binary method to compute \(2^{25}\).

Exercise \(\PageIndex{3}\)

Approximately how many operations would be required to compute \(2^n\) when \(n=10^{100}\)? Explain.

Exercise \(\PageIndex{4}\)

Note that \(6\) multiplications are used to compute \(3^{15}\) using the binary method. Show that one can compute \(3^{15}\) with fewer than \(6\) multiplications. [You will have to experiment.]

Computing \(a^n \bmod m\)

We use the binary method for exponentiation with the added trick that after every multiplication we reduce modulo \(m\), that is, we divide by \(m\) and take the remainder. This keeps the products from getting too big.

Example \(\PageIndex{2}\)

We compute \(3^{15}\bmod 10\): \[\begin{gathered} \begin{aligned} 3^2 &=3\cdot 3=9\equiv 9\pmod{10} \\ 3^4 &=9\cdot 9=81\equiv 1\pmod{10} \\ 3^8 &\equiv 1\cdot 1\equiv 1\equiv 1\pmod{10} \end{aligned} \\ \therefore 3^{15}=3^8\cdot 3^4\cdot 3^2\cdot 3^1\equiv 1\cdot 1\cdot 9\cdot 3=27\equiv 7\pmod{10}.\end{gathered}\] Note that \(3^{15}\equiv 7\pmod{10}\) implies that \(3^{15}\bmod 10=7\). [Recall that on page we calculated that \(3^{15}=14348907\) which is clearly congruent to \(7\bmod{10}\), but the multiplications were not so easy.]

Example \(\PageIndex{3}\)

Let’s find \(2^{644}\bmod{645}\). It is easy to see that \[644=[1,0,1,0,0,0,0,1,0,0]_2\nonumber \] That is, \(644=2^9+2^7+2^2=512+128+4\). Now by successive squaring and reducing modulo \(645\) we get \[\begin{aligned} 2^2 &=2\cdot 2=4\equiv 4\pmod{645} \\ 2^4 &\equiv 4\cdot 4=16\equiv 16\pmod{645} \\ 2^8 &\equiv 16\cdot 16=256\equiv 256\pmod{645} \\ 2^{16} &\equiv 256\cdot 256=65,536\equiv 391\pmod{645} \\ 2^{32} &\equiv 391\cdot 391=152,881\equiv 16\pmod{645} \\ 2^{64} &\equiv 16\cdot 16=256\equiv 256\pmod{645} \\ 2^{128} &\equiv 256\cdot 256=65,536\equiv 391\pmod{645} \\ 2^{256} &\equiv 391\cdot 391=152,881\equiv 16\pmod{645} \\ 2^{512} &\equiv 16\cdot 16=256\equiv 256\pmod{645}.\end{aligned}\] Now \[2^{644}=2^{512}\cdot 2^{128}\cdot 2^4,\nonumber \] hence \[2^{644}\equiv256\cdot 391\cdot 16\pmod{645}.\nonumber \] So \[256\cdot 391=100099\equiv 121\pmod{645}\nonumber \] and \[121\cdot 16=1936\equiv 1\pmod{645}\nonumber \] so we have \(2^{644}\equiv 1\pmod{645}\). Hence \(2^{644}\bmod 645=1\).

Exercise \(\PageIndex{5}\)

Calculate \(2^{513}\bmod 10\).

Exercise \(\PageIndex{6}\)

Calculate \(2^{517}\bmod 100\).

Exercise \(\PageIndex{7}\)

If you multiplied out \(2^{517}\), how many decimal digits would you obtain? [See Exercise 4.3.]

Exercise \(\PageIndex{8}\)

Note that we calculated \(1234^{7865435}\bmod 11\) with very few multiplications. Why can we not use that method to compute \(1234^{7865435}\bmod 12\)?