TWO FAST ALGORITHMS FOR COMPUTING POINT SCALAR MULTIPLICATIONS ON ELLIPTIC CURVES  

作　　者：YouLin WenQiaoyan XuMaozhi 

机构地区：[1]Lab.ofCombinatoricsandInformationScience,HainanNormalUniversity,Halkou571158 [2]P.O.Box126,BeijingUniversityofPostsandTelecom.,Beijing100876 [3]SchoolofMathematics,PekingUniversity,Belting100871

出　　处：《Journal of Electronics(China)》2004年第5期366-375,共10页电子科学学刊（英文版）

基　　金：Supported by the National Natural Science Foundation of China(No.90104004) ;the National 973 High Technology Projects(No.G1998030420)

摘　　要：The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces the corresponding multiplier by modulo Υk-1 +…+Υ+ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve overThe key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Miiller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces thementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free,Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over Fq.

关 键 词：Frobenius endomorphism Frobenius expansion Point scalar multiplication Binary method 

分 类 号：TN918[电子电信—通信与信息系统]