Mathematical analysis of the computational complexity of integer sub-decomposition algorithm

3rd International Conference on Science & Engineering in Mathematics, Chemistry and Physics 2015

数学;化学;物理学

Ajeena, Ruma Kareem K.^1 ; Kamarulhaili, Hailiza^1

School of Mathematical Sciences, Universiti Sains Malaysia, Penang

11800, Malaysia^1

关键词: Computational costs;    Decomposition algorithm;    efficiently-computable endomorphisms;    Elliptic curve;    Finite field operations;    Mathematical analysis;    Mathematical proof;    Scalar multiplication;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/622/1/012032/pdf
DOI  :  10.1088/1742-6596/622/1/012032

来源: IOP

【 摘 要 】

In this paper, the computational complexity to compute a scalar multiplication on classes of elliptic curve over a prime field that have efficiently-computable endomorphismsis analyzed mathematically. 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 mathematical proof of the computational cost of ISD implementation is presented. The computational cost of ISD algorithm has been proven based on the operations counting. Two types of the operations are used, namely, elliptic curve operations represented by elliptic curve point addition A and elliptic curve point doubling D and finite field operations represented by field inversion I, field multiplication M and field squaring S that design the computation of the running time of ISD scalar multiplication.