Exponentiation using Canonical Recoding

Report ID: 
1993-07
Authors: 
Omer Egecioglu and Cetin Kaya Koc
Date: 
1993-04-01 04:00:00

Abstract

The canonical bit recoding technique can be used to reduce the average numberof multiplications required to compute $X^E$ provided that $X^{-1}$ is suppliedalong with $X$. We model the generation of the digits of the canonicalrecoding $D$ of an $n$-bit long exponent $E$ as a Markov chain, and show thatbinary, 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 thesemethods applied to $E$. We show that in general the canonically recoded$m$-ary method for constant $m$ requires fewer multiplications than thestandard $m$-ary method. However, when $m$ is picked optimally for each methodfor a given $n$, then the average number of multiplications required by thestandard method is fewer than those required by the recoded version.

Document

File 1993-07.ps