Left-to-right Generalized Non-adjacent Form Recoding for Elliptic Curve Cryptosystems

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