Analysis of sliding window techniques for exponentiation

The m-ary method for computing xE partitions the bits of the integer E into words of constant length, and then performs as many multiplications as there are nonzero words. Variable length partitioning strategies have been suggested to reduce the number of nonzero words, and thus, the total number of multiplications. Algorithms for exponentiation using such partitioning strategies are termed sliding window techniques. In this paper, we give algorithmic descriptions of two recently proposed sliding window techniques, and calculate the average number of multiplications by modeling the partitioning process as a Markov chain. We tabulate the optimal values of the partitioning parameters, and show that the sliding window algorithms require up to 8% fewer multiplications than the m-ary method.