Left-to-right Generalized Non-adjacent Form Recoding for Elliptic Curve Cryptosystems
Fanyu Kong, Jia Yu, Zhun Cai, Daxing Li · 2006
Various signed digit representations have been used to speed up point multiplication in elliptic curve cryptosystems. In this paper, we present an analysis of the left-to-right radix-r (rges2) generalized non-adjacent form (GNAF) recoding algorithm. A probability model is established to analyze the on-line efficiency of the algorithm. It is proved that the average number of scanned digits required for obtaining one GNAF recoding digit is E(L)= 1 + 1/r-1, with the standard variance sigma(L) = radicr/r-1, and satisfying Pr[L>k] = 1/r(k-1) when k is any positive integer. This algorithm can be used to implement point multiplication in pairing-based cryptosystems and reduce the storage space compared to the right-to-left radix-r (rges2) generalized non-adjacent form (GNAF) recoding algorithm