Editing Exponentiation by squaring (section)

==Sliding-window method==
This method is an efficient variant of the 2<sup>''k''</sup>-ary method. For example, to calculate the exponent 398, which has binary expansion (110 001 110)<sub>2</sub>, we take a window of length 3 using the 2<sup>''k''</sup>-ary method algorithm and calculate 1, x<sup>3</sup>, x<sup>6</sup>, x<sup>12</sup>, x<sup>24</sup>, x<sup>48</sup>, x<sup>49</sup>, x<sup>98</sup>, x<sup>99</sup>, x<sup>198</sup>, x<sup>199</sup>, x<sup>398</sup>.
But, we can also compute 1, x<sup>3</sup>, x<sup>6</sup>, x<sup>12</sup>, x<sup>24</sup>, x<sup>48</sup>, x<sup>96</sup>, x<sup>192</sup>, x<sup>199</sup>, x<sup>398</sup>, which saves one multiplication and amounts to evaluating (110 001 110)<sub>2</sub>

Here is the general algorithm:

Algorithm:

;Input: An element ''x'' of ''G'', a non negative integer {{math|1=''n''=(''n''<sub>''l''−1</sub>, ''n''<sub>''l''−2</sub>, ..., ''n''<sub>0</sub>)<sub>2</sub>}}, a parameter ''k'' > 0 and the pre-computed values <math>x^3, x^5, ... ,x^{2^k-1}</math>.

;Output: The element ''x<sup>n</sup>'' &isin; ''G''.

Algorithm:

 y := 1; i := l - 1
 '''while''' i > -1 '''do'''
     '''if''' n<sub>i</sub> = 0 '''then'''
         y := y<sup>2</sup>
         i := i - 1
     '''else'''
         s := max{i - k + 1, 0}
         '''while''' n<sub>s</sub> = 0 '''do'''
             s := s + 1<ref group="notes">In this line, the loop finds the longest string of length less than or equal to ''k'' ending in a non-zero value. Not all odd powers of 2 up to <math>x^{2^k-1}</math> need be computed, and only those specifically involved in the computation need be considered.</ref>
         '''for''' h := 1 '''to''' i - s + 1 '''do'''
             y := y<sup>2</sup>
         u := (n<sub>i</sub>, n<sub>i-1</sub>, ..., n<sub>s</sub>)<sub>2</sub>
         y := y * x<sup>u</sup>
         i := s - 1
 '''return''' y