A comment on "an efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation"

Da Zhi Sun; Jin Peng Huai; Zhen Fu Cao

doi:10.1016/j.ins.2012.09.052

A comment on "an efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation"

Da Zhi Sun^*
, Jin Peng Huai
, Zhen Fu Cao

^*Corresponding author for this work

Tianjin University
Beihang University
Shanghai Jiao Tong University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

In 2009, Wu proposed a fast modular exponentiation algorithm and claimed that the proposed algorithm on average saved about 38.9% and 26.68% of single-precision multiplications as compared to Dussé-Kaliski's Montgomery algorithm and Ha-Moon's Montgomery algorithm, respectively. However, in this comment, we demonstrate that Wu's algorithm on average reduces the number of single-precision multiplications by at most 22.43% and 6.91%, when respectively compared with Dussé-Kaliski's version and Ha-Moon's version. That is, the computational efficiency of Wu's algorithm is obviously overestimated.

Original language	English
Pages (from-to)	331-334
Number of pages	4
Journal	Information Sciences
Volume	223
DOIs	https://doi.org/10.1016/j.ins.2012.09.052
State	Published - 20 Feb 2013
Externally published	Yes

Keywords

Computational efficiency
Modular arithmetic
Modular exponentiation
Public-key cryptography
Single-precision multiplication

Access to Document

10.1016/j.ins.2012.09.052

Cite this

@article{21901beae7024fe094e058231ddafc23,

title = "A comment on {"}an efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation{"}",

abstract = "In 2009, Wu proposed a fast modular exponentiation algorithm and claimed that the proposed algorithm on average saved about 38.9\% and 26.68\% of single-precision multiplications as compared to Duss{\'e}-Kaliski's Montgomery algorithm and Ha-Moon's Montgomery algorithm, respectively. However, in this comment, we demonstrate that Wu's algorithm on average reduces the number of single-precision multiplications by at most 22.43\% and 6.91\%, when respectively compared with Duss{\'e}-Kaliski's version and Ha-Moon's version. That is, the computational efficiency of Wu's algorithm is obviously overestimated.",

keywords = "Computational efficiency, Modular arithmetic, Modular exponentiation, Public-key cryptography, Single-precision multiplication",

author = "Sun, \{Da Zhi\} and Huai, \{Jin Peng\} and Cao, \{Zhen Fu\}",

year = "2013",

month = feb,

day = "20",

doi = "10.1016/j.ins.2012.09.052",

language = "英语",

volume = "223",

pages = "331--334",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - A comment on "an efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation"

AU - Sun, Da Zhi

AU - Huai, Jin Peng

AU - Cao, Zhen Fu

PY - 2013/2/20

Y1 - 2013/2/20

N2 - In 2009, Wu proposed a fast modular exponentiation algorithm and claimed that the proposed algorithm on average saved about 38.9% and 26.68% of single-precision multiplications as compared to Dussé-Kaliski's Montgomery algorithm and Ha-Moon's Montgomery algorithm, respectively. However, in this comment, we demonstrate that Wu's algorithm on average reduces the number of single-precision multiplications by at most 22.43% and 6.91%, when respectively compared with Dussé-Kaliski's version and Ha-Moon's version. That is, the computational efficiency of Wu's algorithm is obviously overestimated.

AB - In 2009, Wu proposed a fast modular exponentiation algorithm and claimed that the proposed algorithm on average saved about 38.9% and 26.68% of single-precision multiplications as compared to Dussé-Kaliski's Montgomery algorithm and Ha-Moon's Montgomery algorithm, respectively. However, in this comment, we demonstrate that Wu's algorithm on average reduces the number of single-precision multiplications by at most 22.43% and 6.91%, when respectively compared with Dussé-Kaliski's version and Ha-Moon's version. That is, the computational efficiency of Wu's algorithm is obviously overestimated.

KW - Computational efficiency

KW - Modular arithmetic

KW - Modular exponentiation

KW - Public-key cryptography

KW - Single-precision multiplication

UR - https://www.scopus.com/pages/publications/84870255053

U2 - 10.1016/j.ins.2012.09.052

DO - 10.1016/j.ins.2012.09.052

M3 - 文章

AN - SCOPUS:84870255053

SN - 0020-0255

VL - 223

SP - 331

EP - 334

JO - Information Sciences

JF - Information Sciences

ER -

A comment on "an efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation"

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this