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.
public key cryptosystem modular multiexponentiation parallel processing
Chin-Chen Chang Der-Chyuan Lou
Department of Computer Science and Information Engineering Chung Cheng University, Chiayi 621, Taiwa Department of Electrical Engineering Chung Cheng Institute of Technology, Defense University Tahsi,
国际会议
成都
英文
955-958
2003-08-27(万方平台首次上网日期,不代表论文的发表时间)