Exponentiation By Squaring - Sliding Window Method

Sliding Window Method

This method is an efficient variant of the 2k-ary method. For example, to calculate the exponent 398 which has binary expansion (110 001 110)₂, we take a window of length 3 using the 2k-ary method algorithm we calculate 1,x3,x6,x12,x24,x48,x49,x98,x99,x198,x199,x398. But, we can also compute 1,x3,x6,x12,x24,x48,x96,x192,x199, x398 which saves one multiplication and amounts to evaluating (110 001 110)n₂

Here is the general algorithm:

Algorithm:

Input

An element 'x' of 'G',a non negative integer n=(n_l,n_l-1,...,n₀)₂, a parameter k>0 and the pre-computed values x3,x5,....

Output

The element xn in G

Algorithm:

1. y := 1 and i := l-1 2. while i > -1 do 3. if n_i=0 then y:=y2 and i:=i-1 4. else 5. s:=max{i-k+1,0} 6. while n_s=0 do s:=s+1 7. for h:=1 to i-s+1 do y:=y2 8. u:=(n_i,n_i-1,....,n_s)₂ 9. y:=y*xu 10. i:=s-1 11. return y

Note:

1. In line 6 the loop finds the longest string of length less than or equal to 'k' which ends in a non zero value. Also not all odd powers of 2 up to need be computed and only those specifically involved in the computation need be considered.