Editing Exponentiation by squaring (section)

==2<sup>''k''</sup>-ary method==
This algorithm calculates the value of ''x<sup>n</sup>'' after expanding the exponent in base 2<sup>''k''</sup>. It was first proposed by [[Brauer]] in 1939. In the algorithm below we make use of the following function ''f''(0) = (''k'', 0) and ''f''(''m'') = (''s'', ''u''), where ''m'' = ''u''·2<sup>''s''</sup> with ''u'' odd.

Algorithm:

;Input: An element ''x'' of ''G'', a parameter ''k'' > 0, a non-negative integer {{math|1=''n'' = (''n''<sub>''l''−1</sub>, ''n''<sub>''l''−2</sub>, ..., ''n''<sub>0</sub>)<sub>2<sup>''k''</sup></sub>}} and the precomputed values <math>x^3, x^5, ... , x^{2^k-1}</math>.

;Output: The element ''x<sup>n</sup>'' in ''G''

 y := 1; i := l - 1
 '''while''' i ≥ 0 do
     (s, u) := f(n<sub>i</sub>)
     '''for''' j := 1 '''to''' k - s '''do'''
         y := y<sup>2</sup>
     y := y * x<sup>u</sup>
     '''for''' j := 1 '''to''' s '''do'''
         y := y<sup>2</sup>
     i := i - 1
 '''return''' y

For optimal efficiency, ''k'' should be the smallest integer satisfying<ref name="frey">{{cite book |editor1-last=Cohen |editor1-first=H. |editor2-last=Frey, G. |date=2006 |title=Handbook of Elliptic and Hyperelliptic Curve Cryptography |series=Discrete Mathematics and Its Applications |publisher=Chapman & Hall/CRC |isbn=9781584885184}}</ref>

: <math>\lg n < \frac{k(k + 1) \cdot 2^{2k}}{2^{k+1} - k - 2} + 1.</math>