CCS Representation: A New Non-Adjacent Form and its Application in ECC
Abdalhossein Rezai, Parviz Keshavarzi · 2012
This paper introduces CCS (complementary canonical sliding window) representation which is an efficient class of the non-adjacent-form (NAF). The CCS representation is an extension of the complementary representation. The proposed algorithm for converting the integer from the binary representation to the CCS representation uses the complementary method, the canonical recoding method and the sliding window method consecutively. Using Markov chain, we proved that the average Hamming weight of the CCS representation is 80 39 39 w n for n-bit integer with window width w. In elliptic curve cryptosystem (ECC) implementation, the CCS representation is applied on the scalar multiplication to reduce the average number of the point addition/subtraction operation. Our analysis shows that the average Hamming weight of the CCS representation is reduced compared to other representations. Therefore, using the CCS representation in the scalar multiplication, the average number of the point addition/subtraction operation is reduced compared to other scalar multiplication algorithms considerably.