Fast exponentiation based on common-multiplicand-multiplication and minimal-signed-digit techniques

Abstract

In this paper, an improved common-multiplicand-multiplication algorithm is proposed, utilizing the binary exponentiation method and minimal-signed-digit recoding technique for fast exponentiation. By adopting the recoding technique on the common signed-digit representations in the grouped exponent substrings, the proposed algorithm provides an efficient exponentiation method. The proposed algorithm achieves better performance in modern exponentiation methods by decreasing the overall computational complexity. In particular, the proposed method is very suitable for parallel processing systems to improve the efficiency of exponentiation operation.

Keywords:

• Arithmetic algorithm
• Exponentiation
• Multiplication
• Information theory
• Public key cryptography

Additional information

Notes on contributors

Chia-Long Wu

Email: [email protected]