Accelerating Triple Modular Exponentiation: A Novel Technique

Abstract

Modular exponentiation is among the most demanding computational operations in cryptographic systems. Effective computation of modular exponentiation is most beneficial for public-key cryptography. The computational complexity and the growing number of bits of the key size, as required by increasingly stringent security demands in the RSA, the Diffie–Hellman key exchange and the Zero-Knowledge Proof (ZKP) protocols, have become a top research priority in terms of algorithmic efficiency. This study proposes a novel triple modular exponentiation algorithm based on the Improved Common-Multiplicand-Multiplication (ICMM) framework. The exact complexity formula was obtained through systematic probabilistic analysis of eight mutually exclusive bit-level states. The efficiency of modular exponentiation is primarily determined by the number of modular multiplications and exponentiation squares required. It is observed that improved common-multiplicand multiplication efficiently minimizes the computational complexity of the triple modular exponentiation by reducing the number of modular multiplications. The overall computational complexity of triple modular exponentiation is 1.875j, where j is the bit length of the exponent. This represents a reduction of approximately 16.7% in total multiplication count relative to double modular exponentiation, corresponding to a 44.4% reduction on a per-exponent basis, and a reduction of 58.3% relative to three independent binary exponentiations. This study concludes that the proposed decomposition reduces the average-case computational complexity of triple modular exponentiation to 1.875j modular multiplications for a j-bit exponent. The proposed triple modular exponentiation algorithm is shown to have lower number of multiplications per bit length of exponent as compared to double modular exponentiation. This result demonstrates the potential of proposed algorithm to reduce the computational cost of triple modular exponentiation in cryptographic protocols where it is a recurring operation, such as interactive ZKP identification schemes.