Abstract
For modern public key cryptographic systems, the modular cascade exponentiation ((πi=1 pxi ni)modu) is one of the most important arithmetic fundamentals to ensure security. However, the large computing effort needed by this operation also causes the cryptosystems inefficient. The purpose of this paper is to develop some fast methods for computing the modular cascade exponentiation. Two new parallel schemes, called the parallel multi-dimensional binary method and the parallel merging binary method, are proposed. The concept of the shortest parallel vectorial addition chain, which is an optimal approach for parallel computing the modular cascade exponentiation, is also given. The two proposed parallel schemes are faster than the best known serial or parallel modular cascade exponentiation methods. In addition, the computation time of the proposed parallel merging binary method is very close to the lower bound of the shortest parallel vectorial addition chain.