Suppose that you have to compute . If is the binary decomposition of s , then this computation can efficiently be performed as depicted on Fig. 3. Indeed, if we respectively let and the values of z and y at step i (Lines 5 and 7 of Fig. 3), we have and . So,
Square-and-multiply method (I).
Figure 4: Square-and-multiply method (II).
Scanning the bits of exponent s from left to right, we obtain another efficient algorithm to compute (see Fig. 4). The drawback in this algorithm is that it cannot easily be parallelized. Consequently, we only focus on the first algorithm.