Editing Exponentiation by squaring (section)

===Yao's method===
Yao's method is orthogonal to the {{math|2<sup>''k''</sup>}}-ary method where the exponent is expanded in radix {{math|1=''b'' = 2<sup>''k''</sup>}} and the computation is as performed in the algorithm above. Let {{mvar|n}}, {{mvar|n<sub>i</sub>}}, {{mvar|b}}, and {{mvar|b<sub>i</sub>}} be integers.

Let the exponent {{mvar|n}} be written as
: <math> n = \sum_{i=0}^{w-1} n_i b_i,</math>
where <math>0 \leqslant n_i < h</math> for all <math>i \in [0, w-1]</math>.

Let {{math|1=''x<sub>i</sub>'' = ''x<sup>b<sub>i</sub></sup>''}}.

Then the algorithm uses the equality
: <math>x^n = \prod_{i=0}^{w-1} x_i^{n_i} = \prod_{j=1}^{h-1} \bigg[\prod_{n_i=j} x_i\bigg]^j.</math>

Given the element {{mvar|x}} of {{mvar|G}}, and the exponent {{mvar|n}} written in the above form, along with the precomputed values {{math|1=''x''<sup>''b''<sub>0</sub></sup>...''x''<sup>''b''<sub>''w''−1</sub></sup>}}, the element {{mvar|x<sup>n</sup>}} is calculated using the algorithm below:

 y = 1, u = 1, j = h - 1
 '''while''' j > 0 '''do'''
     '''for''' i = 0 '''to''' w - 1 '''do'''
         '''if''' n<sub>i</sub> = j '''then'''
             u = u × x<sup>b<sub>i</sub></sup>
     y = y × u
     j = j - 1
 '''return''' y

If we set {{math|1=''h'' = 2<sup>''k''</sup>}} and {{math|1=''b<sub>i</sub>'' = ''h<sup>i</sup>''}}, then the {{mvar|n<sub>i</sub>}} values are simply the digits of {{mvar|n}} in base {{mvar|h}}. Yao's method collects in ''u'' first those {{mvar|x<sub>i</sub>}} that appear to the highest power {{tmath|h - 1}}; in the next round those with power {{tmath|h - 2}} are collected in {{mvar|u}} as well etc. The variable ''y'' is multiplied {{tmath|h - 1}} times with the initial {{mvar|u}}, {{tmath|h - 2}} times with the next highest powers, and so on.
The algorithm uses {{tmath|w + h - 2}} multiplications, and {{tmath|w + 1}} elements must be stored to compute {{mvar|x<sup>n</sup>}}.<ref name=frey />