Fast Scalar Multiplication Algorithm Based on Frobenius Mapping

Elliptic curve cryptosystem（ECC） is a novel public key cryptosystem, which will be the primary standard for application in the future. The capability of ECC depends on the efficiency of scalar multiplication. Furthermore, fast scalar multiplication algorithm on Koblitz curve is the top demanding task in the research of scalar multiplication. After the reduction of TNAF（k）, a super operation algorithm based on Frobenius mapping is proposed, which is Comb algorithm. At pre-compute stage, in order to establish a pre-compute table, the algorithm calculates the coordinate of some points on elliptic curve corresponding to any sequence at a fixed length of r with the help of Frobenius mapping. On the other hand, at evaluation stage, the algorithm employs the reduction of TNAF（k） as well as the pre-compute table to improve the efficiency of the whole Comb algorithm. Because of high performance of Frobenius mapping, Comb algorithm doesnt relate to point doubling. And after arranging of Comb matrix, the quantity of point addition needed by the algorithm in this paper is 1/5～1/4 times of that needed by traditional algorithms. In addition, the efficiency of the algorithm is faster at least about 67% than the traditional Comb algorithm with arbitrary length of row in any coordinate.