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 -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 -bit numbers is denoted as , then the time complexity of the generalized MSST algorithm is , 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.
Abstract
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 -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 -bit numbers is denoted as , then the time complexity of the generalized MSST algorithm is , 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
{{custom_keyword}} /
Key words
Elliptic curve /
generalized AGM algorithm /
generalized MSST algorithm /
SST algorithm
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Diffie W and Hellman M E, New directions in cryptography, IEEE Transactions on Information Theory, 1976, 22(6):644-654.
[2] Rivest R L, Shamir A, and Adleman L, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 1978, 21(2):120-126.
[3] ElGamal T, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, 1985, 31(4):469-472.
[4] Koblitz N, Elliptic curve cryptosystems, Mathematics of Computation, 1987, 48(177):203-209.
[5] Miller V S, Use of elliptic curves in cryptography, Conference on the Theory and Application of Cryptographic Techniques, Springer Berlin Heidelberg, Berlin, 1985, 417-426.
[6] Schoof R, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, 1985, 44(170):483-494.
[7] Atkin A O L, Morain F, Elliptic curves and primality proving, Mathematics of Computation, 1993, 61(203):29-68.
[8] Atkin A O L and Morain F, Elliptic curves and primality proving, Mathematics of Computation, 1993, 61(203):29-68.
[9] Elkies N D, Explicit Isogenies, Manuscript, Boston, MA, 1992.
[10] Elkies N D, Elliptic and modular curves over finite fields and related computational issues, AMS IP Studies in Advanced Mathematics, 1998, 7:21-76.
[11] Schoof R, Counting points on elliptic curves over finite fields, Journal de théorie des nombres de Bordeaux, 1995, 7(1):219-254.
[12] Satoh T, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, Journal-Ramanujan Mathematical Society, 2000, 15(4):247-270.
[13] Satoh T, Skjernaa B, and Taguchi Y, Fast computation of canonical lifts of elliptic curves and its application to point counting, Finite Fields and Their Applications, 2003, 9(1):89-101.
[14] Gaudry P, A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2, Advances in Cryptology-ASIACRYPT 2002, Ed. by Zheng Y L, Springer-Heidelberg, Berlin, 2002, 311-327.
[15] Mestre J F, Lettre adresséa Gaudry et Harley, http://www.math.jussieu. fr/? mestre, 2000.
[16] Kohel D R, The AGM-X0(N) Heegner point lifting algorithm and elliptic curve point counting, International Conference on the Theory and Application of Cryptology and Information Security, Springer-Heidelberg, Berlin, 2003, 124-136.
[17] Carls R, Explicit Frobenius lifts on elliptic curves, 2009, arXiv:0911.1883.
[18] Karatsuba A, Multiplication of multidigit numbers on automata, Soviet Physics Doklady, 1963, 7:595-596.
[19] Schönhage A, Multiplikation großer Zahlen, Computing, 1966, 1(3):182-196.
[20] Harvey D and Der Hoeven J V, Integer multiplication in time o (n log n), Annals of Mathematics, 2021, 193(2):563-617.
[21] Cohen H, Frey G, Avanzi R, et al., Handbook of Elliptic and Hyperelliptic Curve Cryptography, CRC Press, Boca Raton, 2005.
[22] Vercauteren F, Preneel B, and Vandewalle J, A memory efficient version of Satohs algorithm, International Conference on the Theory and Applications of Cryptographic Techniques, 2001, 2045:1-13.
[23] Vélu J, Isogénies entre courbes elliptiques, CR Acad. Sci. Paris, Séries A, 1971, 273:305-347.
[24] Cox D A. The arithmetic-geometric mean of Gauss, Pi:A Source Book, Springer, New York, 1984.
[25] Carls R, A Generalized Artihmetic Geometric Mean, University Library Groningen[Host], Groningen, 2004.
[26] Kim H Y, Park J Y, Cheon J H, et al., Fast elliptic curve point counting using Gaussian normal basis, Algorithmic Number Theory, Eds. by Fieker C and Kohel D R, Springer-Heidelberg, Berlin, 2002, 2369:292-307.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
This research was supported by the National Natural Science Foundation of China under Grant No. 11701552.
{{custom_fund}}
PDF(269 KB)
