Editing Exponentiation by squaring (section)

==Fixed-base exponent==
There are several methods which can be employed to calculate ''x<sup>n</sup>'' when the base is fixed and the exponent varies. As one can see, [[precomputation]]s play a key role in these algorithms.

===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 />

===Euclidean method===
The Euclidean method was first introduced in ''Efficient exponentiation using precomputation and vector addition chains'' by P.D Rooij.

This method for computing <math>x^n</math> in group {{math|'''G'''}}, where {{mvar|n}} is a natural integer, whose algorithm is given below, is using the following equality recursively:
: <math>x_0^{n_0} \cdot x_1^{n_1} = \left(x_0 \cdot x_1^q\right)^{n_0} \cdot x_1^{n_1 \mod n_0},</math>
where <math>q = \left\lfloor \frac{n_1}{n_0} \right\rfloor</math>.
In other words, a Euclidean division of the exponent {{math|''n''<sub>1</sub>}} by {{math|''n''<sub>0</sub>}} is used to return a quotient {{mvar|q}} and a rest {{math|''n''<sub>1</sub> mod ''n''<sub>0</sub>}}.

Given the base element {{mvar|x}} in group {{math|'''G'''}}, and the exponent <math>n</math> written as in Yao's method, the element <math>x^n</math> is calculated using <math>l</math> precomputed values <math>x^{b_0}, ..., x^{b_{l_i}}</math> and then the algorithm below.

 '''Begin loop'''
     {{nowrap|Find <math>M \in [0, l - 1]</math>,}} {{nowrap|such that <math>\forall i \in [0, l - 1], n_M \ge n_i</math>.}}
     {{nowrap|Find <math>N \in \big([0, l - 1] - M\big)</math>,}} {{nowrap|such that <math>\forall i \in \big([0, l - 1] - M\big), n_N \ge n_i</math>.}}
     '''Break loop''' {{nowrap|if <math>n_N = 0</math>.}}
     {{nowrap|'''Let''' <math>q = \lfloor n_M / n_N \rfloor</math>,}} {{nowrap|and then '''let''' <math>n_N = (n_M \bmod n_N)</math>.}}
     {{nowrap|Compute recursively <math>x_M^q</math>,}} {{nowrap|and then '''let''' <math>x_N = x_N \cdot x_M^q</math>.}}
 '''End loop''';
 {{nowrap|'''Return''' <math>x^n = x_M^{n_M}</math>.}}

The algorithm first finds the largest value among the {{math|''n''<sub>''i''</sub>}} and then the supremum within the set of {{math|{{(}} ''n''<sub>''i''</sub> \ ''i'' ≠ ''M'' {{)}}}}.
Then it raises {{math|''x''<sub>''M''</sub>}} to the power {{mvar|q}}, multiplies this value with {{math|''x''<sub>''N''</sub>}}, and then assigns {{math|''x''<sub>''N''</sub>}} the result of this computation and {{math|''n''<sub>''M''</sub>}} the value {{math|''n''<sub>''M''</sub>}} modulo {{math|''n''<sub>''N''</sub>}}.