Exponentiation using canonical recoding

AbstractThe canonical bit recoding technique can be used to reduce the average number of multiplications required to compute XE provided that X−1 is supplied along with X. We model the generation of the digits of the canonical recoding D of an n-bit long exponent E as a Markov chain, and show that binary, quaternary, and octal methods applied to D require 43 n, 43 n, and 2318 n multiplications, compared to 32 n, 118 n, and 3124 n required by these methods applied to E. We show that, in general, the canonically recoded m-ary method for constant m requires fewer multiplications than the standard m-ary method. However, when m is picked optimally for each method for a given n, then the average number of multiplications required by the standard method is fewer than those required by the recoded version