DocumentCode
25671
Title
Novel RNS Parameter Selection for Fast Modular Multiplication
Author
Yao, Gavin Xiaoxu ; Junfeng Fan ; Cheung, Ray C. C. ; Verbauwhede, Ingrid
Author_Institution
Dept. of Electron. Eng., City Univ. of Hong Kong, Hong Kong, China
Volume
63
Issue
8
fYear
2014
fDate
Aug. 2014
Firstpage
2099
Lastpage
2105
Abstract
The parameter selection of Residue Number Systems (RNS) has a great impact on its computational efficiency. This paper shows that a base extension, the most costly operation in RNS Montgomery multiplication, can be more efficient when the intervals between the RNS moduli are small. We propose a systematic RNS parameter selection procedure and two methods to select RNS moduli that lead to a reduced complexity. Our experimental results confirm the advantages of the selected moduli.
Keywords
computational complexity; public key cryptography; residue number systems; RNS Montgomery complexity; RNS Montgomery multiplication; RNS parameter selection; fast modular multiplication; public key cryptography; residue number system; Modular multiplication; base extension; residue number system (RNS);
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.2013.92
Filename
6504454
Link To Document