Exponentiation By Squaring - Yao's Method

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", "n_i", "b", and "b_i" be integers.

Let the exponent "n" be written as

where for all

Let x_i = xb_i. 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 xb₀....xb_l-1 the element xn is calculated using the algorithm below

1. y=1,u=1 and j=h-1
2. while j > 0 do
3. for i=0 to l-1 do
   1. if n_i=j then u=u*xb_i
4. y=y*u
5. j=j-1
6. return y

If we set h=2k and b_i = hi then the n_i 's are simply the digits of n in base h. Yao's method collects in u first those x_i 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 ).