A basic but expensive operation in implementations of several famous public-key cryptosystems is the computation of the multi-exponentiation in a certain finite multiplication group. In 2007, Yang et al. presented an interesting asynchronous multi-exponentiation algorithm called the SUt method, which uses the binary representations for the exponents. In this note, we analyze the computational efficiency of the SUt method by modeling the scanning process as a Markov chain. It shows that their com
