Parallel computation of the multi-exponentiation for cryptosystems

Some methods of fast modular exponentiation have been proposed in the past years. However, there are only a few parallel mechanisms for evaluating the modular multi-exponentiation. In this paper, we propose two efficient parallel algorithms to speed up the computation of the modular multi-exponentiation Π_i=1ⁿM_i^Ei (mod N), which is an important but time-consuming arithmetic operation used in many scientific researches and applications, especially in the contemporary cryptosystems. We also show that our two proposed methods are faster than the best known sequential method (the Shamir's method) and parallel method (the Chiou's method). Furthermore, our methods can be implemented easily in the multicomputer systems.