Abstract
Modular multi-exponentiation ∏i = 1n MiEi (mod N) 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.
Original language | English |
---|---|
Pages (from-to) | 1065-1074 |
Number of pages | 10 |
Journal | Applied Mathematics and Computation |
Volume | 186 |
Issue number | 2 |
DOIs | |
State | Published - 15 03 2007 |
Externally published | Yes |
Keywords
- Complex arithmetic
- Hamming weight
- Multi-exponentiation
- Public key cryptography
- Signed-digit recoding