Radix-r non-adjacent form and its application to pairing-based cryptosystem

Tsuyoshi Takagi, David Reis, Sung Ming Yen, Bo Ching Wu

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


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 + 1)/2 and its average density of non-zero digit is asymptotically (r - 1)/(2r - 1). For r = 3, the non-trivial digits are (±2, ±4} and the nonzero density is 0.4. We then investigate the width-ω version of rNAF for the general radix-r representation, which is a natural extension of the width-ω 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.

Original languageEnglish
Pages (from-to)115-123
Number of pages9
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number1
Publication statusPublished - Jan 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Radix-r non-adjacent form and its application to pairing-based cryptosystem'. Together they form a unique fingerprint.

Cite this