Hybrid Montgomery reduction

Hwajeong Seo, Zhe Liu, Yasuyuki Nogami, Jongseok Choi, Howon Kim

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


In this article, we present a hybrid method to improve the performance of the Montgomery reduction by taking advantage of the Karatsuba technique. We divide the Montgomery reduction into two sub-parts, including one for the conventional Montgomery reduction and the other one for Karatsuba-aided multiplication. This approach reduces the multiplication complexity of n-limb Montgomery reduction from θ(n2 + n) to asymptotic complexity θ(7n2/8 + n). Our practical implementation results over an 8-bit microcontroller also show performance enhancements by 11%.

Original languageEnglish
Article number58
JournalACM Transactions on Embedded Computing Systems
Issue number3
Publication statusPublished - May 2016


  • Karatsuba multiplication
  • Montgomery reduction
  • Public key cryptography
  • Software implementation

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture


Dive into the research topics of 'Hybrid Montgomery reduction'. Together they form a unique fingerprint.

Cite this