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

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.