Exponentiation By Squaring - 2k-ary Method

2k-ary Method

This algorithm calculates the value of xn after expanding the exponent in base 2k. It was first proposed by Brauer in 1939. In the algorithm below we make use of the following function f(0) = (k,0) and f(m) = (s,u) where m = u·2s with u odd.

Algorithm:

Input
An element x of G, a parameter k > 0, a non-negative integer n = (nl−1, nl−2, ..., n0)2k and the precomputed values x3, x5, ..., .
Output
The element xn in G
1. y := 1 and i := l-1 2. While i>=0 do 3. (s,u) := f(ni) 4. for j:=1 to k-s do 5. y := y2 6. y := y*xu 7. for j:=1 to s do 8. y := y2 9. i := i-1 10. return y

For optimal efficiency, k should be the smallest integer satisfying

Read more about this topic:  Exponentiation By Squaring

Famous quotes containing the word method:

    “In child rearing it would unquestionably be easier if a child were to do something because we say so. The authoritarian method does expedite things, but it does not produce independent functioning. If a child has not mastered the underlying principles of human interactions and merely conforms out of coercion or conditioning, he has no tools to use, no resources to apply in the next situation that confronts him.”
    —Elaine Heffner (20th century)