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)2, 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)n2

Here is the general algorithm:

Algorithm:

Input
An element 'x' of 'G',a non negative integer n=(nl,nl-1,...,n0)2, 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 ni=0 then y:=y2 and i:=i-1 4. else 5. s:=max{i-k+1,0} 6. while ns=0 do s:=s+1 7. for h:=1 to i-s+1 do y:=y2 8. u:=(ni,ni-1,....,ns)2 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.

Read more about this topic:  Exponentiation By Squaring

Famous quotes containing the words sliding, window and/or method:

    “What opium is instilled into all disaster? It shows formidable as we approach it, but there is at last no rough rasping friction, but the most slippery sliding surfaces. We fall soft on a thought.”
    —Ralph Waldo Emerson (1803–1882)

    “I sometimes have the sense that I live my life as a writer with my nose pressed against the wide, shiny plate glass window of the “mainstream” culture. The world seems full of straight, large-circulation, slick periodicals which wouldn’t think of reviewing my book and bookstores which will never order it.”
    —Jan Clausen (b. 1943)

    “The most passionate, consistent, extreme and implacable enemy of the Enlightenment and ... all forms of rationalism ... was Johann Georg Hamann. His influence, direct and indirect, upon the romantic revolt against universalism and scientific method ... was considerable and perhaps crucial.”
    —Isaiah Berlin (b. 1909)