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:
“Traditional scientific method has always been at the very best 20-20 hindsight. Its good for seeing where youve been. Its good for testing the truth of what you think you know, but it cant tell you where you ought to go.”
—Robert M. Pirsig (b. 1928)
Related Phrases
Related Words