Theoretical Computer Science, 129 (1994), pp. 407-417.
Ömer Egecioglu and Cetin K. Koc
Exponentiation using Canonical Recoding
Abstract.
The 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 $\frac{4}{3}n$,
$\frac{4}{3}n$, and $ \frac{23}{18}n $ multiplications, compared to
$\frac{3}{2}n$, $\frac{11}{8}n$, and $\frac{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.
omer@cs.ucsb.edu