Elliptic curve scalar multiplication algorithm using complementary recoding (Q2383732)

Let \(E\) be an elliptic curve defined over a finite field, \(P \in E\) a point on \(E\), and \(k\) an integer. Scalar multiplication on \(E\) is the computation of coordinates of the point \(Q=kP\). If \[ k=k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+ \cdots + k_{1}2+k_{0}, \quad k_{i} \in \{0,1 \}, \] is the standard binary record of \(k\) then scalar multiplication is achieved by repeated elliptic curve point addition and doubling operations. The authors analyze various possible binary records of the number \(k\) and work out an efficient algorithm of scalar multiplication on \(E\) which is based on the use of complementary recording method proposed by \textit{C.C. Chang} at al. in [Proc. of 17th Int. Conf. on Advanced Info. Networking and Applications, March 2003, 807--811 (2003)].