A new algorithm for high-speed modular multiplication design

Ming Der Shieh, Jun Hong Chen, Wen Ching Lin, Hao Hsuan Wu

Research output: Contribution to journalArticlepeer-review

38 Citations (Scopus)


Modular exponentiation in public-key cryptosystems is usually achieved by repeated modular multiplications on large integers. Designing high-speed modular multiplication is thus very crucial to speed up the decryption/encryption process. In this paper, we first explore how to relax the data dependency that exists between multiplication, quotient determination, and modular reduction in the conventional Montgomery modular multiplication algorithm. Then, we propose a new modular multiplication algorithm for high-speed hardware design. The speed improvement is achieved by reducing the critical path delay from the 4-to-2 to 3-to-2 carry-save addition. The resulting time complexity of our development is further decreased by simultaneously performing the multiplication and modular reduction processes. Experimental results show that the developed modular multiplication can operate at speeds higher than those of related work. When the proposed modular multiplication is applied to modular exponentiation, both time and area-time advantages are obtained.

Original languageEnglish
Pages (from-to)2009-2019
Number of pages11
JournalIEEE Transactions on Circuits and Systems I: Regular Papers
Issue number9
Publication statusPublished - 2009

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'A new algorithm for high-speed modular multiplication design'. Together they form a unique fingerprint.

Cite this