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

Recently, signed-digit radix-r   (r⩾2r⩾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-1w(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 left-to-right scalar multiplication, the new representation can reduce both the time and space complexity of the computation compared to the right-to-left wrNAF.