关于素域上的Koblitz曲线  

On Koblitz Curves over Prime Fields

作　　者：伍涵 许光午 WU Han;XU Guang-Wu(Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education,Qingdao 266237,China;School of Cyber Science and Technology,Shandong University,Qingdao 266237,China;Shandong Institute of Blockchain,Jinan 250101,China;Quan Cheng Laboratory,Jinan 250103,China)

机构地区：[1]山东大学密码技术与信息安全教育部重点实验室,青岛266237 [2]山东大学网络空间安全学院,青岛266237 [3]山东区块链研究院,济南250101 [4]泉城实验室,济南250103

出　　处：《密码学报（中英文）》2024年第5期1152-1159,共8页Journal of Cryptologic Research

基　　金：国家重点研发计划(2022YFB2701700,2018YFA0704702);国家自然科学基金(12271306)。

摘　　要：二元扩域F_(2^(m))上的Koblitz曲线Ea属于椭圆曲线密码学中最早一类具有理论和实际意义的曲线,在其上算术运算起重要作用的Frobenius映射τ以下面的方式关联基域的元素个数和有理点的个数:2^(m)=N(τ^(m)),#E_(a)(F_(2^(m)))=N(τ^(m)-1),其中N是Z[τ]上的范,而有理点的个数公式通过zeta函数得出.近来区块链平台中的密码选择使素域上的Koblitz曲线E_(b):y^(2)=x^(3)+b/F_(p)得到关注,这里的素特征p≡1(mod 3).关于Eb的有理点的个数计算已有Rajwade的经典结果,其推导过程与zeta函数并无关系.本文从Rajwade公式得到Eb的有理点的个数的一个简洁表达,只需复数的基本运算,不再涉及平方剩余或立方剩余,也不用列出六个分段情况.本文公式基于Eisenstein整数环Z[ω],证明存在素元π∈Z[ω]和单位u∈Z[ω],使得p=N(π),#E_(b)(F_(p))=N(π-u).这是同二元域上Koblitz曲线的情形完全相似的表达,存在两个Z[ω]中差为一个单位的整数,它们的范分别给出基域的元素个数和曲线上有理点的个数.为此还发展了一些计算三次剩余的工具,包括有理整数的三次剩余的判定,也首次给出了2的三次剩余的确切公式.The well-known class of Koblitz curves Ea over binary fields F_(2^(m))is among the earliest curves in cryptography that are of both theoretical and practical significance.The Frobenius mapτ:E_(a)(F_(2^(m)))→E_(a)(F_(2^(m))),which is critical in the fast arithmetics for this class of Koblitz curves,is also connecting the cardinality of the underlying field and the number of rational points of the curve in the following manner:2^(m)=N(τ^(m)),#E_(a)(F_(2^(m)))=N(τ^(m)-1),where N is the norm over Z[τ],the point counting formula is obtained through zeta function.Recently the cryptographic choice by some platforms of block-chain makes the Koblitz curves Eb:y^(2)=x^(3)+b/F_(p)over a prime field attracting attention,where the prime p≡1(mod 3).There is a classical result of Rajwade for the point counting of Eb/Fp,with a different approach from that using zeta function.Based on Rajwade’s formula,this paper derives a concise expression for the number of points of Eb.Our representation involves only complex arithmetics without quadratic or cubic residues,nor six-piece formula.The new result is in terms of the ring Z[ω]of Eisenstein integers,together with a prime decomposition of p,we prove that there is a primary primeπ∈Z[ω]and a unit u∈Z[ω]such that p=N(π),#E_(b)(F_(p))=N(π-u).This is interesting as it is so similar to the case for binary Koblitz curves:there are two elements of Z[ω]whose difference is just a unit and their norms are the cardinality of the underlying field and the number of rational points of the curve respectively.To this end,we also develop some computational tools for cubic residue,including a whole spectrum for cubic residue character of 2.

关 键 词：KOBLITZ曲线 Eisenstein整数 有理点数 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]