椭圆曲线上点构成加法群.docVIP

论有限域GF(2m)上椭圆曲线的点构成加法群 摘 要　 椭圆曲线理论是代数几何、数论等多个数学分支的一个结合点，一直被认为是纯理论学科。1985年，V.Miller和N.Koblitz各自独立地提出椭圆曲线密码体制。目前，椭圆曲线密码体制在理论和实践上都取得了很大的进展，使用椭圆曲线来构建密码系统的方法研究也取得了比较满意的效果。本文以基础定义开始，以细致的背景如有限域、群概念研究来介绍有限域GF(2m)上椭圆曲线的点构成加法群。 关键词　 椭圆曲线；有限域；GF(2m) ；加法群 ??? 引 言 椭圆曲线密码学（ECC, Elliptic curve cryptography）是基于椭圆曲线数学的一种公钥密码的方法。椭圆曲线在密码学中的使用是在 1985年由Neal Koblitz和Victor Miller分别独立提出的。ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA——提供相当的或更高等级的安全。对椭圆曲线来说最流行的有限域是以素数为模的整数域(参见 模运算)mathGF(p)/math，或是特征为2的伽罗华域GF()。後者在专门的硬件实现上计算更为有效，而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗华域的大小和能力也已经提出了，但被密码专家认为有一点问题。给定一条椭圆曲线E以及一个域mathGF(q)/math，我们考虑具有math(x, y)/math形式有理数点mathE(q)/math的阿贝尔群，其中x和y都在mathGF(q)/math中并且定义在这条曲线上的群运算+在文章椭圆曲线中描述。我们然後定义第二个运算* | Z×mathE(q)-E(q)/math：如果P是mathE(q)/math上的某个点，那么我们定义math2*P=P+P, 3*P=2*P+P=P+P+P/math等等。注意给定整数 j和k，mathj*(k*P)=(j*k)*P=k*(j*P)/math。椭圆曲线离散对数问题(ECDLP)就是给定点P和Q，确定整数k使mathk*P=Q/math。 最简单的有限域是整数环Z 模一个素数p得到的余环Z/(p),由p个元素0,1,…,p-1组成,按模p相加和相乘。集合F={a，b，…}，对F的元素定义了两种运算：“+”和“*”，并满足以下3个条件　　·F1：F的元素关于运算“+”构成交换群，设其单位元素为0。 　·F2：F\{0}的元素关于运算“*”构成交换群。即F中元素排除元素0后，关于*法构成交换群。 　·F3：分配率成立，即对于任意元素　a，b，cF， 　　恒有　　a*(b+c)=(b+c)*a=a*b+a*c p是素数时，可证F{0，1，2，…，p-1}，在modp意义下，关于求和运算“+”，及乘积“*”，构成了域。F域的元素数目有限时称为有限域。 有限域元素的数目称为有限域的阶。对于有限域，其元素的数目必然是素数的幂。而这个对应的素数成为有限域的特征。在编码和密码理论里面2^n阶有限域被广泛使用，具有非常重要的意义。 椭圆曲线就是亏格为1的代数曲线。 一条光滑的椭圆曲线可以放在射影平面里看，它的(仿射)标准方程是y^2=x(x-1)(x-t)， 这里t是任意不等于0和1的参数。 作为实曲面看，椭圆曲线就是带有一个洞的闭曲面－－环面。环面可以通过同向粘合正方形的两对对边得到，其拓扑亏格为1。 椭圆曲线和椭圆函数,椭圆积分等内容密切相关，这里不再详述。 著名的费马大定理的证明也与此有关。总之，椭圆曲线是代数几何中最重要的一类研究对象。 椭圆曲线上的点全体构成一个加法群， 点与点之间的“加法”运算，如图所示。 正因为椭圆曲线存在加法结构，所以它包含了很多重要的数论信息。椭圆曲线和它的雅可比簇是同构的，所以它上面的“加法”结构实际上来自于它的雅可比簇的自然加法结构。 椭圆曲线上的有理点的个数也是人们关心的重要问题，这个问题和著名的Mordell-Weil定理有关。 Mordell-Weil定理是说：椭圆曲线上有理点构成的群是有限生成的。 　　另一方面，椭圆曲线上的整点只有有限多个，这个定理被称为Siegel定理。 通过以下实例，可以更好的理解上述两个定理： 椭圆曲线y^2=x^3+17上，仅有16个整点:(-2,3),(-1,4),(2,5),(4,9),(8,23),(43,282),(52,375),(5234,378661)以及它们关于x轴的对称点，而其上所有的有理点可以由(-2,3),(2,5)通过群上的加法生成。 Bezout定理告诉我们， 两条光滑椭圆曲线相交于9个点（切点重复计算）。 进一步，如果有第三条光滑椭圆曲线经过其中的8个交点，那它必定经过第九个点。这是古典代数几何中的一个重要的结论