Selected RNS Bases for Modular Multiplication

被引：27

作者：

Bajard, J. C. ^{[1
]}

Kaihara, M. ^{[2
]}

Plantard, T. ^{[3
]}

机构：

[1] Univ Montpellier 2, LIRMM, CNRS, F-34095 Montpellier 5, France

[2] Ecole Polytech Fed Lausanne, Lausanne, Switzerland

[3] Univ Wollongong, Wollongong, NSW, Australia

来源：

ARITH: 2009 19TH IEEE INTERNATIONAL SYMPOSIUM ON COMPUTER ARITHMETIC | 2009年

关键词：

CONVERTER; RESIDUE;

D O I：

10.1109/ARITH.2009.20

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The selection of the elements of the bases in an RNS modular multiplication method is crucial and has a great impact in the overall performance. This work proposes specific sets of optimal RNS moduli with elements of Hamming weight three whose inverses used in the MRS reconstruction have very small Hamming weight. This property is exploited in RNS bases conversions, to completely remove and replace the products by few additions/subtractions and shifts, reducing the time complexity of modular multiplication. These bases are specially crafted to computation with operands of sizes 256 or more and are suitable for cryptographic applications such as the ECC protocols.

引用

页码：25 / +

页数：2

共 26 条

[1]

[Anonymous], IEEE T COMPUTERS

[2] A full RNS implementation of RSA [J].

Bajard, JC ;

Imbert, L .

IEEE TRANSACTIONS ON COMPUTERS, 2004, 53 (06) :769-774

[3] Modular multiplication and base extensions in residue number systems [J].

Bajard, JC ;

Didier, LS ;

Kornerup, P .

ARITH-15 2001: 15TH SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 2001, :59-65

[4]

BAJARD JC, 2004, LNCS, V3156, P59

[5]

BAJARD JC, REPORT SELECTED RNS

[6]

CARDARILLI GC, 1998, IEEE T CIRCUITS SY 1, V45

[7]

Cardarilli GC, 2007, CONFERENCE RECORD OF THE FORTY-FIRST ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS & COMPUTERS, VOLS 1-5, P1412

[8]

CIET M, 2003, 46 IEEE INT MW S CIR

[9] New CRT-Based RNS converter using restricted moduli set [J].

Conway, R ;

Nelson, J .

IEEE TRANSACTIONS ON COMPUTERS, 2003, 52 (05) :572-578

[10] FAST COMBINATORIAL RNS PROCESSORS FOR DSP APPLICATIONS [J].

DICLAUDIO, ED ;

PIAZZA, F ;

ORLANDI, G .

IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (05) :624-633

← 1 2 3 →