Algorithm Design and Theoretical Analysis of a New Bit Forwarding Large Integer Modular Exponentiation Algorithm

One of the most principal operations in many PKCs is Modular Exponentiation (ME). This operation is usually performed by successive modular multiplications. So, the efficiency of these PKCs is released on the efficiency of the Modular Multiplication (M2) and modular exponentiation implementation. Therefore, it is essential to minimize the execution time of the M2 and the number of required M2 for performing the ME operation. This paper proposes a novel ME algorithm. In the developed algorithm, the Bit Forwarding (BF) and multibit-scan-multibit-shift techniques are employed for the performance improvement in the ME operation. The complexity analysis is accomplished to show that the developed exponentiation algorithm has benefit in the number of required multiplications. The results indicate that the presented algorithm improves the results compared to other modular exponentiation algorithms by about 11%-85%.