Yao's Method
Yao's method is orthogonal to the 2k-ary method where the exponent is expanded in radix b=2k and the computation is as performed in the algorithm above. Let "n", "ni", "b", and "bi" be integers.
Let the exponent "n" be written as
- where for all
Let xi = xbi. Then the algorithm uses the equality
Given the element 'x' of G, and the exponent 'n' written in the above form, along with the pre computed values xb0....xbl-1 the element xn is calculated using the algorithm below
- y=1,u=1 and j=h-1
- while j > 0 do
- for i=0 to l-1 do
- if ni=j then u=u*xbi
- y=y*u
- j=j-1
- return y
If we set h=2k and bi = hi then the ni 's are simply the digits of n in base h. Yao's method collects in u first those xi which appear to the highest power h-1; in the next round those with power h-2 are collected in u as well etc. The variable y is multiplied h-1 times with the initial u, h-2 times with the next highest powers etc. The algorithm uses l+h-2 multiplications and l+1 elements must be stored to compute xn (see ).
Read more about this topic: Exponentiation By Squaring
Famous quotes containing the word method:
“Letters are above all useful as a means of expressing the ideal self; and no other method of communication is quite so good for this purpose.... In letters we can reform without practice, beg without humiliation, snip and shape embarrassing experiences to the measure of our own desires....”
—Elizabeth Hardwick (b. 1916)