Accelerating Integer Sub-Decomposition for Elliptic Scalar Multiplication using the Generalized wj-NAF Expansions Method
Ruma Kareem, K. Ajeena, Hailiza Kamarulhaili · 2015
In this paper, wNAF expansion method is used to compute a scalar multiplication on classes of elliptic curve over a prime field that have efficiently-computable endomorphisms. This scalar multiplication is called integer sub-decomposition (ISD) method, which is based on the GLV method of Gallant, Lambert and Vanstone that was initially proposed in the year 2001. In this work the ISD implementation uses speed parallel computation of endomorphisms ψi for i = 1,2 to compute the multiple kP of a point P of order n lying on an elliptic curve. The decomposition of a scalar k according to GLV method produces two integers k1 and k2 lie inside the range of ±√n. This decomposition also gives significant number of integers k1 and k2 lie outside the given range of ±√n. These outliers are not considered in the GLV method. Therefore, the ISD approach is proposed to bridge the gap and to complement the GLV method. Besides that, the ISD method helps increase the percentage of successful computation of kP. In this paper, the main idea is to present the parallel computation of ISD elliptic scalar multiplication which is defined by the following decompositions. kP= k11P+ k12ψ1(P)+ k21P+ k22ψ2(P), with |k11|, |k12|, k21|, |k22| < √n. This computation employs two models using the interleaving methods based on parallel computation of the generalized wj-NAF expansions for j=1,2,3,4. It is known that the parallel processing on two proposed interleaving methods produce more computation speed in comparison with the computations that were performed individually.