TY - CHAP
T1 - Radix-r non-adjacent form
AU - Takagi, Tsuyoshi
AU - Yen, Sung Ming
AU - Wu, Bo Ching
PY - 2004
Y1 - 2004
N2 - Recently, the radix-3 representation of integers is used for the efficient implementation of pairing based cryptosystems. In this paper, we propose non-adjacent form of radix-r representation (rNAF) and efficient algorithms for generating rNAF. The number of non-trivial digits is (r - 2)(r + l)/2 and its average density of non-zero digit is asymptotically (r - l)/(2r -1). For r = 3, the non-trivial digits are {±2, ±4} and the non-zero density is 0.4. We then investigate the width-w version of rNAF for the general radix-r representation, which is a natural extension of the width-w NAF. Finally we compare the proposed algorithms with the generalized NAF (gNAF) discussed by Joye and Yen. The proposed scheme requires a larger table but its non-zero density is smaller even for large radix. We explain that gNAF is a simple degeneration of rNAF - we can consider that rNAF is a canonical form for the radix-r representation. Therefore, rNAF is a good alternative to gNAF. Keywords: Non-adjacent form, radix-r representation, signed window method, elliptic curve cryptosystem, pairing based cryptosystem
AB - Recently, the radix-3 representation of integers is used for the efficient implementation of pairing based cryptosystems. In this paper, we propose non-adjacent form of radix-r representation (rNAF) and efficient algorithms for generating rNAF. The number of non-trivial digits is (r - 2)(r + l)/2 and its average density of non-zero digit is asymptotically (r - l)/(2r -1). For r = 3, the non-trivial digits are {±2, ±4} and the non-zero density is 0.4. We then investigate the width-w version of rNAF for the general radix-r representation, which is a natural extension of the width-w NAF. Finally we compare the proposed algorithms with the generalized NAF (gNAF) discussed by Joye and Yen. The proposed scheme requires a larger table but its non-zero density is smaller even for large radix. We explain that gNAF is a simple degeneration of rNAF - we can consider that rNAF is a canonical form for the radix-r representation. Therefore, rNAF is a good alternative to gNAF. Keywords: Non-adjacent form, radix-r representation, signed window method, elliptic curve cryptosystem, pairing based cryptosystem
UR - http://www.scopus.com/inward/record.url?scp=35048820643&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048820643&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-30144-8_9
DO - 10.1007/978-3-540-30144-8_9
M3 - Chapter
AN - SCOPUS:35048820643
SN - 3540232087
SN - 9783540232087
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 99
EP - 110
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Zhang, Kan
A2 - Zheng, Yuliang
PB - Springer Verlag
ER -