Comparative Study of Efficient Modular Exponentiation Algorithms
Ibrahim Marouf, Mohammed Mosab Asad, Qasem S. Abu Al-Haija · Zenodo (CERN European Organization for Nuclear Research) · 2017
This paper presents description on the efficient modular multiplication techniques with numerical examples and flowchart diagrams. This review will help cryptoprocessor designers to in the effective selection of the underlying modular exponentiation unit to improve the hardware cost complexity such as area and speed. We found that conventional techniques of Modular Exponentiation (i.e. L-R binary, R-L binary, Montgomery ladder, and Sliding window) proved its efficiency for many years with average cost complexity of with possibility of saving to multiplications operations for all of the exponent in the case of sliding window. However, the enhanced modular exponentiation based w-NAF and w-MOF are quite up-to-date and will replace all other algorithms as they have the minimum non-zero representation for the exponent. It was shown that NAF representation minimizes the number of nonzero digits in the binary representation, with an average of of nonzero digits while the average non-zero density