본문 바로가기

Hybrid Montgomery Reduction

문서 유형
연구출판물 · 학술지 논문
등재
SCIEScopus
저널 순위
JCR Q3Scopus Q2
피인용
Web of Science 7
JCR IF
JCR 2015 0.714
ISSN
1539-9087

저자

  1. Seo, Hwajeong제1저자Inst Infocomm Res, SI
  2. Liu, Zhe교신저자Univ Waterloo, Waterloo, CN
  3. Nogami, Yasuyuki오카야마대학교, JA
  4. 최종석부산대학교, 정보의생명공학대학, 정보컴퓨터공학부, 정보컴퓨터공학전공, KO
  5. 김호원교신저자부산대학교, 정보의생명공학대학, 정보컴퓨터공학부, 정보컴퓨터공학전공, KO

초록

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 theta(n(2) + n) to asymptotic complexity theta(7n(2)/8 + n). Our practical implementation results over an 8-bit microcontroller also show performance enhancements by 11%.

키워드

Montgomery reductionKaratsuba multiplicationpublic key cryptographysoftware implementationMULTIPLICATIONCRYPTOGRAPHY

식별자

WoS UID
000381422700019