Exponentiation using Canonical RecodingO. Egecioglu and C. K. KocTheoretical Computer Science, 129(2):407-417, 1994.AbstractThe canonical bit recoding technique can be used to reduce the average number of multiplications required to compute X^E 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 (4/3)n, (4/3)n, and (23/18)n multiplications, compared to (3/2)n, (11/8)n, and (31/24)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. |