
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

RNS Montgomery Multiplication Algorithm for Duplicate Processing of Base Transformations
Hanae NOZAKI Atsushi SHIMBO Shinichi KAWAMURA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E86A
No.1
pp.8997 Publication Date: 2003/01/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Asymmetric Ciphers Keyword: RSA cryptography, modular exponentiation, residue number systems, Montgomery multiplication, base transformation,
Full Text: PDF>>
Summary:
This paper proposes a new algorithm to achieve about twotimes speedup of modular exponentiation which is implemented by Montgomery multiplication based on Residue Number Systems (RNS). In RNS Montgomery multiplication, its performance is determined by two base transformations dominantly. For the purpose of realizing parallel processing of these base transformations, i. e. "duplicate processing," we present two procedures of RNS Montgomery multiplication, in which RNS bases a and b are interchanged, and perform them alternately in modular exponentiation iteration. In an investigation of implementation, 1.87times speedup has been obtained for 1024bit modular multiplication. The proposed RNS Montgomery multiplication algorithm has an advantage in achieving the performance corresponding to that the upper limit of the number of parallel processing units is doubled.

