On String Replacement Exponentiation

The string replacement (SR) method was recently proposed as a method for exponentiation a^e in a group G. The canonical k-SR method operates by replacing a run of i ones in a binary exponent, 0exponents. 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.