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

[摘要] 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.

[发布机构] 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