New left-to-right minimal weight signed-digit radix-r representation

✍ Scribed by Baodong Qin; Ming Li; Fanyu Kong; Daxing Li

• Book ID: 104014499
• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 208 KB
• Volume: 35
• Category: Article
• ISSN: 0045-7906
• DOI: 10.1016/j.compeleceng.2008.09.007

✦ Synopsis

Recently, signed-digit radix-r (r P 2) representation is used to speed up the scalar multiplication of pairing based cryptosystems. One such representation is wrNAF proposed by Takagi et al. at the international conference on information security 2004 (ISC 2004). This representation is obtained from right to left. In this paper, we present a new signed-digit radix-r representation with the same average weight, that is rÀ1 wðrÀ1Þþ1 as the wrNAF. The new representation uses the same digits as the wrNAF but has the advantage that it can be deduced using a left-to-right algorithm. Further, we show that like the wrNAF, the new representation has a minimal number of non-zero digits. Interleaved with the leftto-right scalar multiplication, the new representation can reduce both the time and space complexity of the computation compared to the right-to-left wrNAF.