Exponentiation By Squaring - Signed-digit Recoding

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 G is ' fast' or has been precomputed. For example, when computing x2k−1 the binary method requires k−1 multiplications and k−1 squarings . However one could perform k squarings to get x2k and then multiply by x−1 to obtain x2k−1.

To this end we define the signed-digit representation of an integer in radix as

'Signed Binary Representation' corresponds to the particular choice and . It is denoted by . There are several methods for computing this representation. The representation is not unique, for example take . Two distinct signed-binary representations are given by and, where is used to denote . Since the binary method computes a multiplication for every non-zero entry in the base 2 representation of, 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 and denoted by . For example the NAF representation of 478 is equal to . This representation always has minimal Hamming weight. A simple algorithm to compute the NAF representation of a given integer with is the following:

1. for to do
2. return

Another algorithm by Koyama and Tsuruoka does not require the condition that ; it still minimizes the Hamming weight.