On string replacement exponentiation (Q5937085)

The string replacement (SR) method for exponentiation was proposed by \textit{D. Gollmann, Y. Han} and \textit{C. Mitchell} [Des. Codes Cryptography 7, 135-151 (1996; Zbl 0852.94016)]. The canonical \(k\)-SR recoding of \(e\) is the output of the following algorithm: for \(i\) from \(k\) down to 2, starting from the most significant bit of \(e\) and scanning left towards the least significant bit, replace \(1^i\) with \(0^{i-1}b^i\), \(b^i=2^i-1\). In this paper, it is shown that the canonical \(k\)-SR recoding process can be described as a regular language, and the exact probability distribution of recorded exponent weights is derived using generating functions. It is also shown that the canonical \(2\)-SR recoding produces weight distributions very similar to (optimal) signed-digit recording, but no group inversions are required.