On String Replacement Exponentiation

The string replacement (SR) method was recently proposed as a methodfor exponentiation a^e in a group G. The canonicalk-SR method operates by replacing a run of i onesin a binary exponent,0k, with i-1 zeroes followedby the single digit b=2ⁱ-1. After recoding, it was shown in[5] that the expected weight of e tends to n/4 forn-bit exponents. In this paper we show that the canonicalk-SR recoding process can be described as a regular language andthen use generating functions to derive the exact probability distribution ofrecoded exponent weights. We also show that the canonical 2-SR recodingproduces weight distributions very similar to (optimal) signed-digitrecodings, but no group inversions are required.