An Improved Algorithm for Accelerating Modular Exponentiation with Periodic Bit Pattern Exponents

• Kritsanapong Somsuk,
• Nirundon Panit,
• Ravee Phromloungsri,

Vol. 19, No. 4, April 30, 2025
10.3837/tiis.2025.04.011, Download Paper (Free):

• RSA
• modular exponentiation
• Modular multiplication
• periodic bit patterns
• PLR-BE

Abstract

This paper presents a novel approach to improve the efficiency of modular exponentiation computation. In fact, modular exponentiation is essential in public key cryptography, as it can be applied to many algorithms, including RSA, which has been selected for the implementation in this study. In addition, Periodic Left-to-Right Binary Exponentiation (PLR-BE) is introduced, utilizing exponents characterized by periodic bit patterns to reduce the modular multiplication operations. In fact, the proposed method improves the conventional binary exponentiation algorithm by leveraging the repetitive nature of periodic bit patterns, enabling the reutilization of results and thus reducing computational overhead. The implementation of PLR-BE is demonstrated in conjunction with the Chinese Remainder Theorem (CRT) in RSA. This algorithm is called Modified RSA with Periodic Patterns of Sub-private Keys (MRSA-PP). The experimental results show that PLR-BE outperforms the compared techniques, including Left-to-Right Binary Exponentiation (LR-BE) and Right-to-Left Binary Exponentiation (RL-BE), particularly for exponents with high Hamming weights. The efficiency improvements are especially pronounced in the decryption phase of the MRSA-PP. Although, the proposed method does not reduce key sizes, it substantially decreases the time to complete the computation. Furthermore, the proposed method is adaptable and can be applied to other algorithms requiring modular exponentiation for the computation to decrease computation resources.

Statistics

Cite this article