Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Analyzing and Comparing Montgomery Multiplication Algorithms

Cetin K. Koc and Tolga Acar


This article discusses several Montgomery multiplication algorithms, two of which have been proposed before. We describe three additional algorithms, and analyze in detail the space and time requirements of all five methods. These algorithms have been implemented in C and in assembler. The analyses and actual performance results indicate that the Coarsely Integrated Operand Scanning (CIOS) method, detailed in this article, is the most efficient of all five algorithms, at least for the general class of processor we considered. The Montgomery multiplication methods constitute the core of the modular exponentiation operation which is the most popular method used in public-key cryptography for encrypting and signing digital data.


Publication typeArticle
Published inIEEE Micro
PublisherIEEE Computer Society
> Publications > Analyzing and Comparing Montgomery Multiplication Algorithms