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
For optimal efficiency, k should be the smallest integer satisfying
Read more about this topic: Exponentiation By Squaring
Famous quotes containing the word method:
“I know no method to secure the repeal of bad or obnoxious laws so effective as their stringent execution.”
—Ulysses S. Grant (18221885)
Related Phrases
Related Words