Editing Exponentiation by squaring (section)

==Signed-digit recoding==
In certain computations it may be more efficient to allow negative coefficients and hence use the inverse of the base, provided inversion in {{mvar|'''G'''}} is "fast" or has been precomputed. For example, when computing {{math|''x''<sup>2<sup>''k''</sup>−1</sup>}}, the binary method requires {{math|''k''−1}} multiplications and {{math|''k''−1}} squarings. However, one could perform {{mvar|k}} squarings to get {{math|''x''<sup>2<sup>''k''</sup></sup>}} and then multiply by {{math|''x''<sup>−1</sup>}} to obtain {{math|''x''<sup>2<sup>''k''</sup>−1</sup>}}.

To this end we define the [[signed-digit representation]] of an integer {{mvar|n}} in radix {{mvar|b}} as
: <math>n = \sum_{i=0}^{l-1} n_i b^i \text{  with  } |n_i| < b.</math>

''Signed binary representation'' corresponds to the particular choice {{math|1=''b'' = 2}} and <math>n_i \in \{-1, 0, 1\}</math>. It is denoted by <math>(n_{l-1} \dots n_0)_s</math>. There are several methods for computing this representation. The representation is not unique. For example, take {{math|1=''n'' = 478}}: two distinct signed-binary representations are given by <math>(10\bar 1 1100\bar 1 10)_s</math> and <math>(100\bar 1 1000\bar 1 0)_s</math>, where <math>\bar 1</math> is used to denote {{math|−1}}. Since the binary method computes a multiplication for every non-zero entry in the base-2 representation of {{mvar|n}}, we are interested in finding the signed-binary representation with the smallest number of non-zero entries, that is, the one with ''minimal'' [[Hamming weight]]. One method of doing this is to compute the representation in [[non-adjacent form]], or NAF for short, which is one that satisfies <math>n_i n_{i+1} = 0 \text{ for all } i \geqslant 0</math> and denoted by <math>(n_{l-1} \dots n_0)_\text{NAF}</math>. For example, the NAF representation of 478 is <math>(1000\bar 1 000\bar 1 0)_\text{NAF}</math>. This representation always has minimal Hamming weight. A simple algorithm to compute the NAF representation of a given integer <math>n = (n_l n_{l-1} \dots n_0)_2</math> with <math>n_l = n_{l-1} = 0</math> is the following:

 {{nowrap|<math>c_0=0</math>}}
 for {{math|1=''i'' = 0}} to {{math|''l'' − 1}} do
   {{nowrap|<math>c_{i+1} = \left\lfloor\frac{1}{2}(c_i + n_i + n_{i+1})\right\rfloor</math>}}
   {{nowrap|<math>n_i' = c_i + n_i - 2c_{i+1}</math>}}
 {{nowrap|return <math>(n_{l-1}' \dots n_0')_\text{NAF}</math>}}

Another algorithm by Koyama and Tsuruoka does not require the condition that <math>n_i = n_{i+1} = 0</math>; it still minimizes the Hamming weight.