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:
“... [a] girl one day flared out and told the principal the only mission opening before a girl in his school was to marry one of those candidates [for the ministry]. He said he didnt know but it was. And when at last that same girl announced her desire and intention to go to college it was received with about the same incredulity and dismay as if a brass button on one of those candidates coats had propounded a new method for squaring the circle or trisecting the arc.”
—Anna Julia Cooper (18591964)