Fast Parallel Computation of Multi-Exponentiation for Public Key Cryptosystems

Multi-exponentiation may be performed faster than the traditional multiple square and multiply method by rearranging the exponentiation in an efficient sequence. For a suitable choice of such sequences, the resulting multi-exponentiation reduces the expected number of non-squaring multiplications at the cost of a rearrangement. Rearrangement effort depends entirely on the exponent and can be kept down to the work saved in a single exponentiation. Some methods of fast exponentiation have been proposed in the past years to make the implementation of public key cryptosystems easier; however, there are only a few parallel mechanisms for evaluating the modular multi-exponentiation. In this paper, we propose a parallel algorithm for modular multi-exponentiation. A fast and efficient implementation for this new parallel algorithm is also sketched. Besides, our parallel algorithm can be employed with other existing methods for further speedup. Both hardware and software implementations of the multi-exponentiation can benefit from this algorithm.