ANALYSIS OF SLIDING WINDOW TECHNIQUES FOR EXPONENTIATION

The m-ary method for computing x(E) partitions the bits of the integer E into words of constant length, and then performs as many multiplica tions as there are nonzero words. Variable length partitioning strateg ies have been suggested to reduce the number of nonzero words, and thu s, the total number of multiplications. Algorithms for exponentiation using such partitioning strategies are termed sliding window technique s. In this paper, we give algorithmic descriptions of two recently pro posed sliding window techniques, and calculate the average number of m ultiplications by modeling the partitioning process as a Markov chain; We tabulate the optimal values of the partitioning parameters, and sh ow that the sliding window algorithms require up to 8% fewer multiplic ations than the m-ary method.