1.26: Computation of aⁿ 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 first method’s steps \[a^2=a\cdot a, \quad a^3=a^2\cdot a, \quad a^4=a^3\cdot a, \quad \dotsc, \quad 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 exponent laws \[\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 1. Find the binary representation \[n=\left[a_r,a_{r-1},\dotsc,a_0\right]_2\nonumber \] for \(n\).
• Step 2. Compute the powers \[x^2,x^{2^2},x^{2^3},\dotsc,x^{2^r}\nonumber \] by successive squaring as shown above.
• Step 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 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 \[2^r\le n\le 2^r+2^{r-1}+\dotsb+2+1=2^{r-1}-1<2^{r+1}.\nonumber \] Since \(\log_2\left(2^x\right)=x\) and when \(0<a<b\) we have \(\log_2(a)<\log_2(b)\), the inequalities above yield \[\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\frac1{0.69314718}\,\ln(x) \approx 1.442695\,\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\).

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.

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 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\).

Exercises

Exercise \(\PageIndex{1}\)

Calculate \(3\lfloor\log_2(n)\rfloor\) for \(n=\text{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.)

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 1.6.9.)

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\)?