Fast modular multi-exponentiation using modified complex arithmetic

Modular multi-exponentiation Pi M-n(i=1)i(E)i(modN) is a very important but time-consuming operation in many modern cryptosystems. In this paper, a fast modular multi-exponentiation is proposed utilizing the binary-like complex arithmetic method, complement representation method and canonical-signed-digit recoding technique. By performing complements and canonical-signed-digit recoding technique, the Hamming weight (number of 1's in the binary representation or number of non-zero digits in the binary signed-digit representations) of the exponents can be reduced. Based on these techniques, an algorithm with efficient modular multi-exponentiation is proposed. For modular multi-exponentiation, in average case, the proposed algorithm can reduce the number of modular multiplications (MMs) from 1.503k to 1.306k, where k is the bit-length of the exponent. We can therefore efficiently speed up the overall performance of the modular multi-exponentiation for cryptographic applications. (c) 2006 Elsevier Inc. All rights reserved.