Institution: | aSchool of Computer Science and Technology, Tianjin University, No. 92 Weijin Road, Nankai District, Tianjin 300072, PR China bSchool of Computer, Beihang University, Beijing 100083, PR China |
Abstract: | Very recently, for speeding up the computation of modular multi-exponentiation, Wu et al. presented a fast algorithm combining the complement recoding method and the minimal weight binary signed-digit representation technique. They claimed that the proposed algorithm reduced the number of modular multiplications from 1.503k to 1.306k on average, where the value k is the maximum bit-length of two exponents. However, in this paper, we show that their claim is unwarranted. We analyze the computational efficiency of Wu et al.’s algorithm by modeling it as a Markov chain. Our main result is that Wu et al.’s algorithm requires 1.471k modular multiplications on average. |