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:

    “With these I would be.
    And with water: the waves coming forward, without cessation,
    The waves, altered by sand-bars, beds of kelp, miscellaneous
    driftwood,
    Topped by cross-winds, tugged at by sinuous undercurrents
    The tide rustling in, sliding between the ridges of stone,
    The tongues of water, creeping in, quietly.”
    —Theodore Roethke (1908–1963)

    “It is a pleasure to stand upon the shore, and to see ships tossed upon the sea: a pleasure to stand in the window of a castle, and to see a battle and the adventures thereof below: but no pleasure is comparable to standing upon the vantage ground of truth ... and to see the errors, and wanderings, and mists, and tempests, in the vale below.”
    —Francis Bacon (1561–1626)

    ““English! they are barbarians; they don’t believe in the great God.” I told him, “Excuse me, Sir. We do believe in God, and in Jesus Christ too.” “Um,” says he, “and in the Pope?” “No.” “And why?” This was a puzzling question in these circumstances.... I thought I would try a method of my own, and very gravely replied, “Because we are too far off.” A very new argument against the universal infallibility of the Pope.”
    —James Boswell (1740–1795)