The idea of the GLV method of Gallant, Lambert and Vanstone (Crypto 2001) is considered a foundation stone to build a new procedure to compute the elliptic curve scalar multiplication. This procedure, that is integer sub-decomposition (ISD), will compute any multiple kP of elliptic curve point P which has a large prime order n with two low-degrees endomorphisms ψ1 and ψ2 of elliptic curve E over prime field F p . The sub-decomposition of values k 1 and k 2, not bounded by ±C n , gives us new integers k 11, k 12, k 21 and k 22 which are bounded by ±C n and can be computed through solving the closest vector problem in lattice. The percentage of a successful computation for the scalar multiplication increases by ISD method, which improved the computational efficiency in comparison with the general method for computing scalar multiplication in elliptic curves over the prime fields. This paper will present the mechanism of ISD method and will shed light mainly on the computation complexity of the ISD approach that will be determined by computing the cost of operations. These operations include elliptic curve operations and finite field operations.

Contents IJPAM: Volume 87, No. 1 (2013)

In this study, we introduce the probability distribution of the elliptic curve scalar multiplication through finding the probability distribution of the secret key, namely, the scalar k of the scalar multiplication kP of a point P which has a large prime order n lying on elliptic curve group E(F p ) over a finite prime field F p . To determine this distribution of k, we use the integer sub-decomposition (ISD) approach that inspired from Gallant, Lambert and Vanstone (GLV) idea. In ISD approach, the distribution of the values of scalars k lie outside the range ± n on the interval [1, n − 1]. This distribution determines the successful rate to compute a scalar multiplication kP, on ISD approach, in comparison with the original GLV method. The conception of the ISD approach depends on the sub- decomposition of the scalar k to compute the scalar multiplication kP which uses efficiently computable endomorphisms Ψ1 and Ψ2 of elliptic curve E over F p . The ISD sub-decomposition can be defined by k P = k 11 P + k 12 ψ 1 ( P ) + k 21 P + k 22 ψ 2 ( P ) , with max { | k 11 | , | k 12 | } and max { | k 21 | , | k 22 | } ≤ C n , for some explicit constant C > 0. Furthermore, this study compares between the GLV and ISD approaches on the basis of the probability distribution of the scalar k in the interval [1, n − 1], where n is a large prime number.

This article discusses a mixed graph called mixed hourglass graph. The adjacency of a mixed hourglass graph is coined from an hourglass matrix in which the matrix is obtained from quadratic interlocking factorization. Mixed hourglass graph is a weighted graph with loops, but replacing the weights of the graph with 1’s produce an unweighted mixed hourglass graph or simply mixed hourglass graph. Then the total number of arcs and edges and the spanning subgraph of mixed hourglass graph are examined to infer that the graph is a complete mixed graph and acyclic graph.