On String Replacement Exponentiation

Abstract

The string replacement (SR) method was recently proposed as a method for exponentiation ae in a group G. The canonical k-SR method operates by replacing a run of i ones in a binary exponent, O < i ≤ k, with i - 1 zeroes followed by the single digit b = 2i - 1. After recoding, it was shown in [5] that the expected weight of e tends to n/4 for n-bit exponents. In this paper we show that the canonical k-SR recoding process can be described as a regular language and then use generating functions to derive the exact probability distribution of recoded exponent weights. We also show that the canonical 2-SR recoding produces weight distributions very similar to (optimal) signed-digit recodings, but no group inversions are required.