Computational efficiency analysis of Wu et al.'s fast modular multi-exponentiation algorithm

摘要

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 Wit 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. (c) 2007 Elsevier Inc. All rights reserved.