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 条
[11]  
DIDIER LS, EEE T CIRCU IN PRESS, V2
[12]   NEW DIRECTIONS IN CRYPTOGRAPHY [J].
DIFFIE, W ;
HELLMAN, ME .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (06) :644-654
[13]  
HOSSEINZADEH M, 2008, 10 ICACT 2008, V3, P1601
[14]  
JOHNSON D, MENEZES ELLIPTIC CUR
[15]  
KOBILITZ N, 1987, ELLIPTIC CURVE CRYPT, V48, P203
[16]   USE OF ELLIPTIC-CURVES IN CRYPTOGRAPHY [J].
MILLER, VS .
LECTURE NOTES IN COMPUTER SCIENCE, 1986, 218 :417-426
[17]  
MONTGOMERY PL, 1985, MATH COMPUT, V44, P519, DOI 10.1090/S0025-5718-1985-0777282-X
[18]   A HIGH-SPEED REALIZATION OF A RESIDUE TO BINARY NUMBER SYSTEM CONVERTER [J].
PIESTRAK, SJ .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-ANALOG AND DIGITAL SIGNAL PROCESSING, 1995, 42 (10) :661-663
[19]   MODULE REDUCTION IN RESIDUE NUMBER-SYSTEMS [J].
POSCH, KC ;
POSCH, R .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1995, 6 (05) :449-454
[20]   AN RNS TO BINARY CONVERTER IN 2N + 1, 2N, 2N - 1 MODULI SET [J].
PREMKUMAR, AB .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-ANALOG AND DIGITAL SIGNAL PROCESSING, 1992, 39 (07) :480-482
123