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:
“English! they are barbarians; they dont believe in the great God. I told him, Excuse me, Sir. We do believe in God, and in Jesus Christ too. Um, says he, and in the Pope? No. And why? This was a puzzling question in these circumstances.... I thought I would try a method of my own, and very gravely replied, Because we are too far off. A very new argument against the universal infallibility of the Pope.”
—James Boswell (17401795)