Editing Exponentiation by squaring (section)

===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>}}.