A w-NNAF method for the efficient computation of scalar multiplication in elliptic curve cryptography

Based on the non-adjacent form (NAF) expression, here we present a new method to express a large positive integer k with the base of any positive integer w other than 2. We call this method the w-NNAF method as the expression is near to the NAF one and with base w. This expression leads to the minimal Hamming weight of all the base w expressions. Based on the proposed expression and some existing methods, an algorithm is developed to compute kP efficiently.