A Generalized MSST Algorithm for Counting Points of Elliptic Curves over F_(p)^(n)  

作　　者：LI Xiao LV Chang PAN Zhizhong 

机构地区：[1]Key Laboratory of Cyberspace Security Defense,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100085,China [2]School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100085,China [3]Huawei Technologies Co.,Ltd.,Shenzhen 518129,China

出　　处：《Journal of Systems Science & Complexity》2024年第4期1738-1754,共17页系统科学与复杂性学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant No.11701552。

摘　　要：Elliptic curve cryptography is an important part of nowaday's public key cryptosystem.Counting points of elliptic curves over finite fields is of great significance to the selection of safety curves.At present,there are many p-adic algorithms,such as SST algorithm,generalized AGM algorithm,Kedlaya algorithm,etc.,which can deal with the situation of finite fields of small characteristics.In this paper,the authors generalize the MSST algorithm of characteristic 2 to general fields of odd characteristic,and propose the generalized MSST algorithm.The generalized MSST algorithm is achieved by combining the advantages of the SST algorithm and the generalized AGM algorithm.If the time complexity of the multiplication of two n-bit numbers is denoted as O((n)^(μ)),then the time complexity of the generalized MSST algorithm is O(n^(2μ+1/1+μ)),which is the same as the improved SST algorithm.In practical experiments,the running time of the generalized MSST algorithm is less than that of the improved SST algorithm.

关 键 词：Elliptic curve generalized AGM algorithm generalized MSST algorithm SST algorithm 

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