Efficient Multithreading Computation of Modular Exponentiation with Pre-computation of Residues for Fixed-base
Ihor Prots’ko, A. Gryshchuk, Volodymyr Riznyk · 2023
Modular exponentiation is an important operation in many applications that requires a large number of operations.Efficient computations of the modular exponentiation are extremely necessary for efficient computations for provide high crypto capability of information data and in many other applications.Modular exponentiation is implemented using of the development of the right-to-left binary exponentiation method for a fixed base with precomputation of redused set of residuals.To efficient compute the modular exponentiation over big numbers, the property of a periodicity for the sequence of residuals of a fixed base with exponents equal to an integer power of two is used.The multithreading software implementation of modular exponentiation is described.The MPIR library with an integer data type with the number of binary digits from 256 to 2048 bits is used to develop an algorithm for computing the modular exponentiation.Comparison of the runtimes of four variants of functions for computing the modular exponentiation is performed.In the algorithm with pre-computation of residues for fixed-base provide faster computation of modular exponentiation compared to the functions of modular exponentiation of the MPIR, OpenSSL and Crypto++ libraries.