## 10.5 Computing Modular Powers  For an element \[*m*\]*n* ∊ **Z***n* and nonnegative integer *k*, the problem of computing  is called the *problem of computing modular powers.* [Examples 10.43](LiB0083.html#1105) and [Examples 10.44](LiB0083.html#1106) showed the computation of some modular powers. Another example follows. Example 10.51**** In [Example 10.51](#ch10ex89) we determined the power simply by taking 7 to the 11th power. Clearly, this method has exponential time complexity in terms of the input size (approximately the logarithms of the numbers). Next we develop a more efficient algorithm. **** The algorithm requires we represent *k* as a binary number. Let  be the ordered set of binary digits in that representation. For example, since the binary representation of 13 is 1101, if *k* = 13,  The algorithm now follows. We say that the algorithm uses the method of ***repeated squaring.*** The reason is obvious. Algorithm 10.4 Compute Modular Power****Problem: For an element \[*m*\]*n* ∊ **Z**n and nonnegative integer *k*, compute (\[*m*\]*n*)*k.* **** Inputs: positive integer *n*, and nonnegative integers *m* and *k.* Outputs: (\[*m*\]*n*)*k.* ``` void compute_power (int n, int m, int k, Znmember& a) { index i; a = [1]n; {bj, bj-1, . . ., b1, b0} = ordered set of digits in binary representation of k; for (i = j; i >= 0; i - -) a = a2; if (bi = = 1) a = a×[m]n; } ``` Next we show an example of applying [Algorithm 10.4](#ch10ex90). Example 10.52****Suppose ****  Since the binary representation of 45 is 101101,  [Table 10.2](#ch10table02) shows the state of *a* after each iteration of the **for**-*i* loop in [Algorithm 10.4](#ch10ex90) given this input. The final value of *a*, namely \[147\]257, is the value of (\[5\]257)45. Table 10.2: The state of *a* after each iteration of the for-*i* loop in [Algorithm 10.4](#ch10ex90) when *n* = 257, *m* = 5, and *k* = 45. The third row shows the value determined by the high-order *j* - *i* + 1 bits in the binary representation of *k.*i 5 4 3 2 1 0 bi 1 0 1 1 0 1 ki 1 2 5 11 22 45 a \[5\]257 \[25\]257 \[41\]257 \[181\]257 \[122\]257 \[147\]257 In [Table 10.2](#ch10table02), *ki* is the value determined by the high-order *j* - *i* + 1 bits in the binary representation of *k.* That is,  For example,  Clearly, *k*0 = *k.* We will use these variables to prove the correctness of the algorithm, which we do next. Theorem 10.26****After each iteration of the **for**-*i* loop in [Algorithm 10.4](#ch10ex90), ****  Since *k*0 = *k*, this means the final value of *a* is (\[*m*\]*n*)*k.* Proof: The proof is by induction. Induction base: We assume a minimal binary representation; so the high-order bit *bj* equals 1. Therefore,  Before entering the **for**-*i* loop, *a* = \[1\]*n.* Since *bj* equals 1, the **if** condition is true in the first iteration, which means the instruction *a* = *a*×\[*m*\]*n* executes. Therefore, we have  after the first iteration. Induction hypothesis: Suppose after the iteration with index value *i* that  Induction step: We need to show that, after the iteration with index value (*i* - 1),  There are two cases: If *bi*-1 = 0, clearly  Since the condition in the **if** statement is false, only the instruction *a* = *a*2 changes the value of *a.* Since by the induction hypothesis the previous value of *a* is (\[*m*\]*n*)*ki*, we have  after this iteration. If *bi*-1 = 1, clearly  Since the condition in the **if** statement is true, the instruction *a* = *a*×\[*m*\]*n* also executes. So in this case,  after this iteration. It is straightforward that, if we let *s* be the number of bits it take to encode the input, the time complexity of [Algorithm 10.4](#ch10ex90) is in *O*(*s*3).