An efficient divide-and-conquer technique for parallel computation of modular multi-exponentiation

A lot of research and system developments on the public key cryptosystem have been done in the last decade. In most of famous public key cryptosystems, the main task of the encryption and decryption engine is to compute the modular multi-exponentiation ∏_i=1ⁿM_i^Ei (mod N), where all the values of E_i's are positive integers and n is equal to or greater than one. Several methods of fast exponentiation have been proposed in the past years to make the implementation of public key cryptosystems easierhowever, there are only a few parallel mechanisms for evaluating the modular multi-exponentiation. In this paper, we propose an efficient method for parallel computation of modular multi-exponentiation. On average, the time complexity of our proposed method for computing ∏_i=1ⁿM_i^Ei(mod N) is O(k_max/2ⁿ) multiplication time units, where k_max is the maximal bit-length among all bit-lengths of E_i's.