Implementing Montgomery Multiplication to Speed-Up the Computation of Modular Exponentiation of Multi-Bit Numbers

A comparison and analysis of using the developed software implementation of the MontgomeryArithmetic class for computing modular exponentiation are conducted. The performance speed of the developed Montgomery modular multiplication is compared to that of the regular modular multiplication for calculating the modular exponentiation based on the right-to-left binary method for a fixed basis with precomputation of a reduced set of residues. The obtained results of modular exponentiation computing with parallelization based on multithreading on general-purpose computers speed up the computation by an average of 1.5 times using the developed modular Montgomery multiplication compared to the modular exponentiation functions of the MPIR, OpenSSL, and Crypto++ software libraries.