On String Replacement Exponentiations

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, i greater than 0 and less than or equal to k, with i - 1 zeroes followed by by the single digit b = 2**i - 1. After recoding, it was shown in [D. Gollman et al., Designs, Codes and Cryptography, vol. 7, p. 135 (1996)] 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.