Exponentiation By Squaring

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 = (n_l−1, n_l−2, ..., n₀)_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(n_i) 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