（基础数学专业论文）两类超椭圆曲线同构类的计数.pdf

摘要 1 9 8 5 年e m i l l e r 和n k o b l i 忽分别独立地提出了椭圆曲线密码体制( e c c ) ，经过二 十多年的研究，e c c 已广泛应用于许多商业领域。1 9 8 9 年k o b l i 忽把椭圆曲线推广到更 高亏格的超椭圆曲线。利用e c c 的所有构造，只需将椭圆曲线的加法点群用超椭圆曲 线的j a e o b i a n 群来替换，我们就可以实现超椭圆曲线密码体制( 砸c c ) 。在保持同等 安全的条件h e c c 可以使用较小的密钥长度。如定义在有限域c 上亏格2 的超椭圆曲 线( 其中q = 2 ) 与定义在有限域上的椭圆曲线的点群e ( v q ) ( 其中q 。2 1 砷) 和定义在 v ( = 0 2 4 ) 上的乘群达到相同的安全级。o q 2 i 经过二十来年的研究，有限域上亏格大于4 的超椭圆曲线被证明是不安全并不适用 做密码体制，也就是说从安全上考虑合适做密码体制的超椭圆曲线的亏格必须小于或等 于4 。为了知道有多少条合适的安全曲线，把有限域上的超椭圆曲线进行分类是必要的， 而有限域上亏格等于2 或者3 的超椭圆曲线的分类前人也有了很好的分析。 本文中，我们主要给出了有限域v 。( p 2 ，3 ) 上亏格4 的超椭圆曲线同构类的数目， 与此同时，我们还给出了有限域上p i c a r d 曲线( p 2 ，3 ) 同构类的数目。这些结果可用于 分类问题和超椭圆曲线密码体制的研究。 关键词：超椭圆曲线；p i c a r d 曲线；有限域；同构类 a b s t r a c t s i n c ee l l i p t i cc a lv ec r y p t o s y s t e m s ( e c c ) w e r ep r o p o s e di na r o u n d1 9 8 5 ，e c ch a sb e e n s t u d i e df o ra b o u tt w e n t yy e a r sa n dh a sb e e nr e c e n t l ya p p l i e di nm a n yc o m m e r c i a lp u r p o s e s i n19 8 9 ，k o b l i t zg e n e r a l i z e dt h ec o n c e p to fe l l i p t i cc u r v ec r y p t o s y s t e m st o h y p e r e l l i p t i c c u r v e so fh i g h e rg e n u s u s i n gt h ej a c o b i a no fah y p e r e l l i p t i cc u r v ed e f i n e do v e raf i n i t ef i e l d i n s t e a do fa ne l l i p t i cc h i v eo v e raf i n i t e f i e l d ，w ec a nf u r t h e rr e d u c et h ek e ys i z ew h i l e m a i n t a i n i n gt h es a m el e v e lo fs e c u r i t y o n ec a nu s eah y p e r e l l i p t i cc u r v eo fg e n u s2o v e ra f i n i t ef i e l d ，w h e r eq = 2 ，a n da c h i e v et h es a m el e v e lo fs e c u r i t ya sw h e na ne l l i p t i c c u r v eg r o u p e ( f q ) i su s e d ，w h e r eq z 2 1 6 0o ra g r o u p w i t hq _ - 2 1 0 2 4 i su s e d h y p e r e l l i p t i cc u r v e so v e rf i n i t ef i e l d sh a v eb e e ns t u d i e df o rc r y p t o g r a p h yf o rt w e n t y y e a r sa n dt h eh y p e r e l l i p t i cc u r v e so fg e n u sl a r g e rt h a n4h a v eb e e np r o v e du n s a f ea n d u n s u i t a b l ef o rp r a c t i c a lc r y p t o s y s t e m s f o rs e c u r i t yc o n s i d e r a t i o n s ，h y p e r e l l i p t i cc u r v e su s e d f o rc r y p t o s y s t e m ss h o u l db eo fg e n u sn ol a r g et h a n4 i no r d e rt ok n o wh o w m a n ys u i t a b l e c h o i c e so fc u r v e sf o rc r y p t o g r a p h i cp u r p o s e st h e r ea r e ，i t m a yb eu s e f u lt oc l a s s i f yt h e i s o m o r p h i s mc l a s s e so fh y p e r e l l i p t i cc u r v e so v e rf i n i t ef i e l d s t h en u m b e ro fi s o m o r p h i s m c l a s s e so fh y p e r e l l i p t i cc u r v e so f g e n u s2o r3o v e r p q h a db e e ns t u d i e di np r e v i o u sw o r k s i nt h i sp a p e r , t h en u m b e ro f i s o m o r p h i s mc l a s s e so fh y p e r e l l i p t i cc u r v e so fg e n u s4o v e r af i n i t ef i e l dw i t hc h a r a c t e r i s t i cd i f f e r e n tf r o m2 ，3i sg i v e n ，w h a t sm o r e ，w e a l s og i v et h e n u m b e ro ft h ei s o m o r p h i s mc l a s s e so fp i c a r dc u r v e sd e f i n e do v e rf i n i t ef i e l d s f 扩( p 2 ，3 ) ， a n dt h e s ec l a s s i f i c a t i o n sa r eo fi n t e r e s ti nd e s i g n i n ga n di m p l e m e n t i n g h y p e r e l l i p t i cc u r v e c r y p t o s y s t e m s k e y w o r d s ：h y p e r e l l i p t i cc u r v e s ；p i c a r dc u r v e s ；f i n i t ef i e l d s ；i s o m o r p h i s mc l a s s e s l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。除文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得海南师范大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：耄缝丝 日 学位论文著作权声明 本论文作者声明： 口本论文全部成果均为本人和指导教师合作研究取得，本人和指导教师都有权使 用本成果学术内容( 有第三方约定者除外) 。 口本论文为指导教师指导下，本人独自完成。本人独自享有 学位论文作者签名：霉曼罄一 日期：递旦墨：墨：垒 指导教师签名： 日期： 学位论文版权使用授权书 权。 本学位论文作者完全了解海南师范大学有关保留、使用学位论文的规定，即：海南 师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子文本，允许论 文被查阅和借阅。本人授权海南师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：童主墨盘 日期：坦2 星：壶：芝 指导教师签名： 第一章绪论 当前，信息技术与产业的发展正处于空前繁荣的阶段。以i n t e r n e t 为代表的计算机网 络的迅速发展和广泛应用，正引起社会和经济的深刻变革。i n t e r n e t 已经成为我们生活和 工作中的一个不可分割的组成部分。基于计算机网络的“电子政务”、“电子商务”和“电 子金融”正在兴起，它们的兴起在政务、商务和金融领域引起了一场革命。然而，由于 i n t e r n e t 的开放性和无政府状态，使i n t e r n e t 成为一个不安全的网络。这就使得i n t e r n e t 不 能适应电子政务、电子商务和电子金融等系统对信息安全的需要。网络安全和信息安全 已经成为发展电子政务、电子商务和电子金融的主要技术瓶颈。迄今为止，公钥密码技 术是解决这些问题最有效的方法。 1 9 7 6 年，w d i f f i e 和m h e l l m a n n3 发表了“密码学的新方向( n e wd i r e c t i o n s 伽c r y p t o g r a p h y ) 一文，提出了一种崭新的密码设计思想，导致了密码学的一场革命。即公开 密钥密码学的研究与应用。 1 9 8 5 年，v m i l l e r 乜3 和n k o b l i t z 嘲分别独立地提出了椭圆曲线密码体制( e c c ) ，e c c 是基于有限域上的椭圆曲线的有限加法点群的公钥密码体制。经过2 0 多年的研究，近几 年已经被广泛应用于实际中。 作为e c c 的推广，n k o b l i t z h l 在1 9 8 9 年提出了超椭圆曲线密码体制( h e c c ) ，即利用 有限域上超椭圆曲线上的j a c o b i a n 群来构造公钥密码体制。 g a l b r a i t h ，p a u l u s 和s m a r t 嫡3 于2 0 0 0 年把超椭圆曲线推广到了超级椭圆曲线( s u p e r - p z 幼t i cc u r v e s ) ，并提出了用超级椭圆曲线上的j a c o b i a n 群来构造公钥密码体制。 1 1 课题的研究背景及其意义 当前主要的公钥算法大致基于下面不同的数学问题。它们分别是大整数分解问题、 离散对数问题、椭圆曲线离散对数问题。 ( 1 ) 大整数分解问题i f p ( i n t e g e rf a c t o r i z a t i o np r o b l e m ) ：计算两个大素数的乘积不 难，但是将一个大的整数分解为其素因数的乘积非常困难。其代表性产品有r s a 密码系 统等： ( 2 ) 离散对数问题d l p ( d i s c r e t el o g a r i t h mp r o b l e m ) ：设n 为正整数，如果对于每个 与n 互素的x ，都存在一个整数z ，使得g 。= x m o d n 成立的整数g 存在，则称整数g 海南师范大学硕+ 学位论文 是模n 的一个本原根，具备这一特性的整数z 称为x 的以g 为底模，l 的离散对数。其中模 指数运算是频繁的用于密码学中的一种单向函数。即计算a r o o d n 是容易的，但它的逆 问题：求解方程a = b ( m o d n ) 中的x 是个难题。也就是找出这个数的离散对数是困难的。 对这一思想的抽象，可通过利用循环群的生成元代替本原根的方式实现同样的过程。代 表性产品有d s a 数字签名系统等： ( 3 ) 椭圆曲线离散对数问题e c d l p ( e l l i p t i cc u r v ed l p ) ：椭圆曲线密码是基于有限 域上有理点群的一种密码系统，其数学基础是利用椭圆曲线上的点构成的a b e l i a n 加法 群构造的离散对数的计算困难性。代表性的密码产品有e c c 。 总体来说，自从1 9 7 6 年d i f f i e h e l l m a n 公钥密码的思想提出以来，国际上已经提出了 许多种公钥密码体制。而应用于设计公钥密码体制的群主要有以下几种： ( 1 ) 历上的单位群，其中n 是整数畸7 8 9 1 0 1 1 1 2 1 3 1 利； ( 2 ) 有限域上乘法群的真子群n 氧1 6 , 1 7 ； ( 3 ) 有限域上椭圆曲线的有理点群乜，3 1 ； ( 4 ) 有限域上超椭圆曲线的j a c o b i a n 群n 1 ； ( 5 ) 虚二次数域类群n 引； ( 6 ) 有限域上超级椭圆曲线的j a c o b i a n 群哺1 。 人们之所以对这些群感兴趣是由于它们的群运算很容易在硬件或者软件上实施 1 9 ，但潜在的计算问题却非常困难( 即解大整数分解问题或离散对数问题在计算上是 困难的) 。 目前解决这类问题的最好算法是数域筛法( g n f s ) 2 0 , 2 1 , 2 2 , 2 3 , 2 4 , 2 5 当n = n ( 对于整 数分解问题) 和n = p ( 对于离散对于问题) 的亚指数期望运行时间是 三呈 e x p ( ( 1 9 2 3 + o ( 1 ) ) ( 1 0 9 ) 3 ( 1 0 9 l o g ) 3 ) 。 因此为了避免g n f s 攻击，整数的选择必须足够大。2 0 0 6 年字节长1 0 2 4 比特的整数 被认为中度安全。为了更高的安全着想，必须使用更大的模。比如说，在一些受限的 计算环境实施离散对数加密系统使用群z ：是不可行的，比如智能卡以及手持式无线设 备( 如移动电话和传呼机) 啪1 o 在下文中我们局限于考虑有限域上的椭圆曲线，超( 级) 椭圆曲线的群在d l p 上 的设计。这类群上的加密技术能够使用比其它群上较小的模数却保持相同的安全防护 2 第一章绪论 级别。这对减小密钥，节省带宽，快速实现是非常重要的。 定义在有限域上的椭圆曲线e 上的有理点群e ( 巴) 广泛应用于密码学中( 即e c c ) 汹瑚瑚1 。该群的点加运算是基于其有限群上的算术运算。由h a s s e 定理，该群的阶大约 等于鼋，如果阶的最大素因子为n ，则解决e ( c ) 上离散对数问题最好算法是( p o l l a r d s r h o 算法m 1 ) 大约执行亚指数时间d ( i ) 步，即有限域乞上的椭圆曲线( q z2 1 砷) 与 群z ： ( p z 2 0 2 4 ) 有相同的安全级口刳。 表一是n i s t 所推荐的用于标准加密算法的密钥大小。 表一：n i s t 标准加密算法的密钥大小 椭圆曲线密码体制( e c c ) 的优势表明，在实践中，它们更适合于更高更持久的安 全应用程序，以至于把它们用在国家安全问题上。此外，有几个有关e c c 的密钥交换 计划，加密破译议定书，以及数字签名方案标准已开发，举例说，国际标准化组织( 巧d ) ， a n s i 和的i e e e b 3 棚1 。美国政府在国家标准技术研究院( n i s t ) 用e c c 作为密钥协议和 数字签名方案姐4 瑚3 ，用以保护机密数据。同样地，美国国家安全局( n s a ) 采用相关协 议计划以保障国家安全。其他政府机构也在开发这些密码如：加拿大通信安全组织) ( c a 汜) ，德国国防部长署( g e d ) ，美国联邦航空管理局( 明洒) ，以及加拿大邮 政( c p ) 。此外，椭圆曲线也被用于很多大公司，例如，微软( w i n d o w s 媒体播放器) ， 日立，英特尔，索尼和东芝( 5 c 内容保护以及数字传输内容保护) 。 一般来说，可以使用任何代数曲线的j a c o b i a n 群来构造离散对数问题。但是这样做， 出现两个困难： ( 1 ) 如何从每个除子类中选择一个标准表达式， ( 2 ) 对于给定的两个除子类的标准表达式，如何计算两个除子类的和的标准表达 海南师范大学硕士学位论文 式。 当采用定义在有限域上的超椭圆曲线时这些问题是可以适当地解决。如果c 是定义 在有限域上的超椭圆曲线则有限域上j a c o b i a n 群的阶( 记为j c ( ) ) 大约是譬3 。如果 g = 1 ，超椭圆曲线即是椭圆曲线。 当亏格g 很大时，有一个基于a d l e m a n ，d e m a r r a i s 和h u a n g 的亚指数算法汹1 来解 决超椭圆曲线上的离散对数问题。此外，当g 3 时存在比p o l l a r d sr h o 算法更快的算 法口7 勰3 钉。如果g = 2 或g = 3 ，刀是l ( c ) 的最大素除子，那么最好的算法需要花指数时 间d ( ，1 ) 步。因此，可以使用定义在有限域c 上亏格2 的超椭圆曲线( 其中q 2 8 0 ) 与 定义在有限域上的椭圆曲线的点群e ( c ) ( 其中q z 2 1 6 0 ) 达到相同的安全级。 但是，超椭圆曲线密码体制也有缺点，最显著的是j a c o b i a n 的运算法则要比e c c 的群运算法则复杂，且确定j a c o b i a n 的阶比较困难。从已有的h e c c 的实现来看，h e c c 的实现速度并不理想，但由于h e c c 可以提供更少的带宽，并且需要更小的基域，从而 有许多e c c 所不具备的优点。超椭圆曲线还可应用于p r i m a l i t y 证明、整数分解、纠错 码分析等领域畸2 瑚埘3 。虽然目前h e c c 的实现不理想，但是可以相信，一旦有了有效的 算法，h e c c 必将成为主流密码体制强有力的竞争对手，特别是带宽和内存受限的应用 ( 如智能卡) 。h e c c 具有上述优点，所以h e c c 仍有很大的研究必要。况且，只有对 它作深入研究，才能发现更高效的算法，才能使得它早日走向成熟。 最近，p e l z l 等人m “嵋表明，低成本的应用亏格4 的超椭圆曲线可以超越亏格2 的 超椭圆曲线。为了实现超椭圆曲线密码体制，其基本的运算是k d 的计算，其中k 是一 个大素数( 一般为较大的整数) ，d 是j a c o b i a n 群中的元素。因为这种密码体制的安全 性依赖于解群j ( 兄) 中的离散对数问题的困难性( 即超椭圆曲线离散对数问题 ( h e c d l p ) 。如果q = 2 7 ，那么r 必须是一个素数防止耽豇攻击。为了抵制t a t e - p a i r i n g 攻击，q 5 三l ( m o d p ) 中的s 必须大于2 0 h 霸。此外，亏格g 必须小于5 以防止g a u d r y 陋7 1 提出的算法攻击。从而在研究超椭圆曲线密码体制时只考虑亏格2 、3 和4 的超椭圆曲 线。 为了研究h e c c ，首先人们需要回答有多少条有限域上的超椭圆曲线可用于密码体 制，因为同构的两条超椭圆曲线的j a c o b i a n 群作为a b e l 群是同构的，两条同构的超椭 4 第一章绪论 圆曲线从密码学的角度来说是相同的，于是问题变为计算超椭圆曲线的同构类数目。对 于亏格2 的情形，e n c i n a s 等n 研给出了当有限域特征c 妇厂( ) 2 ，5 时上的亏格2 超椭 圆曲线的同构类数目的公式：对c h a r ( c ) = 2 ，y c h o i e 等h 钔分三类情况解决了其同构问 题并给出了确切的公式；我国学者邓映蒲等m 3 对特征2 亏格2 的t y p e 勿r 曲线的计数提出 了一种新方法，简化了计算过程：对c h a r ( f q ) = 5 ，e n c i n a s 和m a s q u e h 刀给出了类似的公 式：最近e n c i n a s 等啪1 又给出了一篇关于亏格2 超椭圆曲线综述性比较强的论文。对于亏 格3 的情形，j e o n g 等h 钔给出了当有限域特征c h a r ( f q ) 2 ，7 时c 上的亏格3 超椭圆曲 线的同构类数目的公式：之后对c h a r ( c ) = 7 ，文嘞3 给出了亏格3 超椭圆曲线所有表达式 的界。 不过，几个有关亏格4 的超椭圆曲线密码相关问题是需要回答的。如以下几方面： ( 1 ) 不同超椭圆曲线及其j a c o b i a n 群的元素代表的标准表达式必须确定； ( 2 ) 希望存在一个更为有效的算法的表达式； ( 3 ) 亏格4 的超椭圆曲线应归类，必须为每个同构类找到一个”简单”的标准表达式； ( 4 ) f r e y 和r i i c k $ 妇表明，如何使在一个超椭圆曲线的j a c o b i a n 群约减为某个潜在有 限域的延拓。该超椭圆曲线的约减表达式必须有效，而且应该归类。 1 2 本文所做的工作 超椭圆曲线密码体制目前虽然还主要是停留在研究阶段，但已有很多专利产生旧1 ， 估计很快就可以投入使用。本文介绍了亏格4 的超椭圆曲线同构类的计算；为了方便读 者，首先从一类简单的p i c a r d 曲线的同构类出发，再以定义在有限域上的亏格4 的超椭 圆曲线为研究对象，对以下几个方面进行研究并取得了相应的成果： 1 有限域上p i c a r d 曲线的奇异方程的个数； 2 分类讨论并计数特征c h a r ( g ) 2 ，3 时有限域c 上的p i c a r d 曲线的同构类目； 3 有限域上亏格4 的超椭圆曲线奇异方程的个数； 4 分类讨论并计算特征c 砌，( ) 2 ，3 时有限域上的亏格4 的超椭圆曲线的同 构类数目； 5 对下一步工作进行了展望和归纳。 本论文比较成功地将有限域上亏格4 的超椭圆曲线密码进行了分类，这些结果有利 5 海南师范人学硕士学位论文 于解决曲线的分类问题和公钥密码体制的研究。 1 3 论文的章节安排 第二章中主要介绍了与超椭圆曲线密码相关的数学背景知识，如有限域，抽象代数 群论，数论，及超椭圆曲线的定义等等。 第三章主要介绍了p i c a r d 曲线及其同构类的计算技巧，为下一章有限域上亏格4 的超椭圆曲线的同构类的计数做好铺垫。其中得出了p i c a r d 的曲线的奇异方程和同构类 的个数，并对其做了很好的分类。 第四章是本文的关键结果，计数了有限域上亏格4 的超椭圆曲线奇异方程的个数， 分类讨论并计数特征c h a r ( f q ) 2 ，3 时有限域c 上的亏格4 的超椭圆曲线的同构类数 目。这些结果可用于分类问题和超椭圆曲线密码体制研究。 最后是本论文的总结，并对未来的工作提出了展望。 6 第二章超椭圆曲线的基本理论 在本章中，我们给出有限域上超椭圆曲线基本理论的一个介绍。超椭圆曲线作为代 数几何的一个研究内容，具有很高深的理论知识。我们只是给出一个与密码密切相关的 有限域上超椭圆曲线的一些基本性质的介绍，所需知识不超过抽象代数( 有关抽象代数 的基本知识可以参考文献 5 5 ，5 6 ，5 7 ，5 8 ) ，所有定理和性质只是列出而没有给出证明。 有关超椭圆曲线理论的更详细的知识可以参看文献 5 9 6 0 。 2 1 有限域的基本知识 定义2 1 1 设( f ，斗x ) 上是交换环，如果满足： ( 1 ) f 中至少含有两个元素q 和l 。 ( 2 ) f = f o ) 构成乘法群。 那么称( f ，+ 为是域。 具有有限个元素的域称为有限域。f = 纠p z ( p 为素数) 是最简单的有限域。 设表示特征为p 且含有g 个元素的有限域，我们知道，可以看成艺上的向量空 间，设维数为d ，则q = p 8 。 定义2 1 2 素域 设p 是一个素数，以p 为模，则模p 的全体余数的集合 o ，1 ，2 ，p - 1 ) 关于模p 的 加法和乘法构成一个p 阶有限域，并用符号表示。我们称p 为c 的模。对于任意的 整数日，口m o d p 表示用p 除口所得到的余数，0 r p 一1 ，并称这种运算为求模p 的 剩余。 定义2 1 3 二进制域 阶为2 ”的域称为二进制域或特征为2 的有限域。构成只。的一种方法是采用多项式 基表示法。在这种表示法中，域只。的元素是次数最多为m 一1 次的二进制多项式( 多项 式的系数取自e = o ，1 ) ) ， 7 海南师范大学硕士学位论文 = n 。一l z ”1 + 一2 z ”2 + + 口2 2 2 + q z + ：口j o ，1 ) ) 。 选择一个二进制域上的m 次既约多项式，( z ) ( 对于任意的m ，这样的多项式一定存在， 就一定能有效产生 6 1 ) 。，( z ) 的既约性恿味看厂( z ) 不能被分解成次数低于m 的二进制 域上的多项式的乘积。域元素的加法是两个多项式系数的模2 相加。域元素的乘法是两 个多项式相乘后取模厂( z ) 。对于任意一个二进制域上的多项式口( z ) ，a ( z ) m o d f ( z ) 表示 一个次数低于m 的余式多项式，( z ) 。余式多项式，( z ) 可用，( z ) 辗转相除口( z ) 得到，这一 运算称为求模厂( z ) 的余式。 定理2 1 1 设乞是含有g = 个元素的有限域，令仃：8h 口p ，则仃是乞上的一 个自同态。 定理2 1 2 设巧是含有g = p 。个元素的有限域，那么的子域为艺。( 其中皿) 。 密码学上用得最广的两个有限域，是大素数有限域艺( p 为大素数) 和特征为2 的 有限域。 下面给出有限域中元素常见的表示方法： ( 1 ) 有限域艺。的多项式基 对于任意给定的k 2 ，总存在艺m 上的k 次不可约多项式m ( x ) ，则 乞。兰e z 】沏( z ) ) ，乞。也可以看作m ) 的一个根秒添加到c 所得到的最小扩域有限 域0 。实际上是e 上的足维向量空间，设矽是m ) 在0 t 上的一个根，则 汐，秒2 ，口卜1 ) 在 c 上线性无关，构成向量空间的一组基在多项式基表下，c 。中的元素可以看成次数小 于k 的多项式。 ( 2 ) 有限域艺。的元素口l 。称为c 上的正则元，如果口，矿，扩“1 在巴上线性 无关此时称 口，扩，口p 卜1 ) 为0 上0 。的一组正则基。 2 2 数论和群论的知识 定理2 2 ie 6 2 有限域c 上阶数为m 的首1 不可约多项式的个数为 8 第二章超椭圆曲线的基本知识 n p ( m ) = 去萎( d ) q 州d ，其中“( d ) 为默比乌斯函数，其定义为 f 1若d = 1 ， ( d ) = 0 若d 可被素数的平方整除， l ( 一1 ) 若d 是t 个不同的素数之乘积。 其中1 是g 的单位元。对口x ，在口处的稳定子瓯是如下定义的子群： 瓯= g g l g a = o c ) ， 包含口的轨道g 口= g 口陪g ) 的长度由轨道一稳定子公式决定： 阱禺。 对g g ，g 的不动点集舡x ( g ) 定义如下： 豇x ( g ) = 口x i g 翻= 轨道个数七由b “m j i d e 引理确定： 七2 高薹 肛x ( g ) j 定理2 2 4 硒设p 为事素数，模p 的缩系中有三( p 1 ) 个二次剩余，有三( p 1 ) 个 9 海南师范大学硕士学位论文 二次非剩余，且 即为所有的模p 二次剩余。 1 2 2 2 ，( 三( p _ 1 ) ) 2 定理2 2 5 ( 容斥原理) 集s 的不具有只，只，己的物体的个数由下式给出： i 石n 石r 、n 石i = i s i 一i a i + l an a ，i 一i ar 、4n a l + + ( 一1 ) ”i an an n i ( 2 2 1 ) 其中，第一个和对 1 ，2 ，m ) 的所有的1 一组合埘进行，第二个和对 l ，2 ，m ) 的所有 的2 一组合 f ，歹) 进行，第三个和对 1 ，2 ，掰) 的所有的3 一组合 f ，j ，k ) 进行等等。 如果 t = 3 ，式( 2 2 1 ) 变为 f - 厂、石厂、石l = 蚓一( i a l + l 如l + i a f ) + ( 1 4 厂、如l + 1 4 厂、如 + i 如n 1 ) 一l ar 、如n l 。 注意上式右边有i + 3 + 3 + 1 = 8 项。如果m = 4 ，式( 2 2 i ) 变为 | _ n 石n 石r 、石l = 蚓一( + | 如i + i 如i + i a 4 1 ) + ( 1 an 如f + i an a i + i an a f + i ar 、 f + i 如na 4 i + f 如n a f ) - ( ar 、如广、a | + l an 如na 4 l + i 如n ana 4 1 ) + i an a 厂、 厂、a 4 l 。 在这种情况下，右边共有1 + 4 + 6 + 4 + 1 = 1 6 项。在这种情况下，式( 2 2 1 ) 右边的项数为 ( 孑) + ( ? ) + ( ) + ( 了) + + ( ：) = 2 ”。 2 3 超椭圆曲线 本节中我们给出了一些超椭圆曲线的基本定义和定理。 设是g 个元素的有限域，是的代数闭包。上的亏格g ( g i ) 的超椭圆曲 线c 是一条定义于上的亏格g 的射影非奇异不可约曲线，使得存在从c 到p 1 ( ) 中 的二次映射，其中p 1 ( 0 ) 表示上的1 维射影空间。同文献 4 3 一样，我们进一步假 1 0 第二章超椭圆曲线的基本知识 设c 有一有理点p ，使得c 的一有理函数域有非常数函数，其唯一的极点是二重极 点p 。这样的点叫w e i e r s t r a s s 点。用h 。记上的亏格g 的超椭圆曲线全体之集。 两条日。中的曲线称为在上同构，如果它们作为上的射影簇是同构的。简而言 之，两条c 上的射影簇v ，k 是同构的，则存在映射矽：v k ，缈：k k ，使得矽。缈 和缈。矽是单位映射。 上的同构关系是日。上的等价关系。如果日。中的两条曲线c l ， c 2 在上同构，则它们的j a c o b i a nj q ( ) 和，c 2 ( ) 作为a b e l 群是同构的，但是反 过来不对。亏格g 的超椭圆曲线分类与h e c c 有关，因为它们的j a c o b i a n 群可用于构 造d l p 问题。 定义2 3 1 上亏格g 的w e i e r s t r a s s 方程e 是 工，y 】中如下形式的方程： e f ：y 2 + 办( 工) y = ，( 工) ， 其中 ( 工) ，厂( 工) c 【工】，d e g ( h ) g ，d e g ( f ) = 2 9 + 1 且，( 工) 是首1 多项式，方程无奇 异的仿射点，也就是说不存在( 五) ，) f x f 同时满足e ( x ，y ) = y 2 + 办( 工) y 一，( 工) ，以及该 方程的偏导巨( 工，y ) ，b ( 工，y ) 。用记所有亏格g 的w e i e r s t r a s s 方程之集。 命题2 3 1 6 0 在日。中曲线的同构类和取中w e i e r s t r a s s 方程的等价类之间存在 一一对应，其中h ，h 2 取称为在上等价，是指存在口，且t r io ，及 f ( 工) c 【x 】，d e g ( t ) g ，使得坐标变换 ( 工，) ，) ( 口2 工+ ，矿8 + 1 y + f ( 工) ) 把方程日，变为了h ：。这样， , - t - 数h 。中曲线的同构类数目，只需计算吼中w e i e r s t r a s s 方程的等价类数目。它是w g 在命题2 3 1 中坐标变换下的轨道数目。本文第四章所说的 坐标变换均指命题2 3 1 中的坐标变换。 第三章有限域上p i c a r d 曲线的同构类 为了研究超椭圆曲线的同构类，本人研究了一种简单的代数曲线p i c a r d 曲线，它是 形如y 3 = ，( 工) ( 其中，( 工) 是次数为4 的非奇异( 判别式( 厂) 0 ) 首一多项式) 的超级椭 圆曲线( s u p e r e l l i p t i cc u r v e s ) 。通过对p i c a r d 曲线的研究，更好地了解有限域上亏格4 的 超椭圆曲线的运算过程。 3 1 p i c a r d 曲线的一般表达式 命题3 1 1 5 9 有限域上特征不等于3 的p i c a r d 曲线是同构的，是指曲线方程 c ：y 3 = 工4 + 口3 x 3 + a 6 x 2 + a 9 x + a 1 2 和 否：y 3 - - x 4 i 一a 3 x 3 + i 彬2 + i + i ， 存在 a ，p f q ， 且 口0 ，( 工，) ，) - - - ( 矿工+ ，a 4 y ) ， 把方程c 化为了c 。这样，计数p i c a r d 曲线的同构类数目，只需计数方程中的( 厂) 0 的 等价类数目。 在此变量代换下，p i c a r d 曲线方程系数满足下列等式： 口3 i = 4 + 吧 口6 竺2 6 2 + 3 夕口3 + 口6 ( 3 1 1 ) 口9 a 9 = 4 p 3 + 3 2 a 3 + 2 伽6 + a 9 2 一a 1 2 = + 3 如+ 2 口6 + 肋9 + q 2 命题3 。1 。2 定义在上特征2 ，3 的任意条p i c a r d 曲线都可以表示为如下方程： y 3 = 工4 + 口6 x 2 + a 9 x + o a 2 。 如果日，h 是定义在上的同构曲线，即 h ：y 3 = 工4 + 口6 x 2 + a g x + a _ 1 2 ， 1 2 第三章有限域上p i c a r d 曲线的同构类 h ：y 3 - x 4 + a 6 x 2 - l - a 9 x - i - a 1 2 ， 由方程日到日存在唯一的容许变换 ( 五) ，) 一( 矿工，a 4 y ) ，a e l 矿口6 - - a 6 a 9 a 9 = a 9 ( 3 1 2 ) l 口坦口1 2 = 口1 2 证明： 通过变量代换工= 一x + a 4 3 $ 1 罐ly = 歹，方程y 3 = 工4 + 口3 x 3 + 口6 x 2 + 口9 z + q 2 变为 y 3 = 工4 + 口6 x 2 + a g x + t h 2 ，即定义在乞上特征2 ，3 的任意条p i c a r d 曲线都可以表示为如 ( x ，y ) j ( 矿工，t 2 4 y ) ，a e 3 2 c h a 厂( c ) 2 ，3 时的同构类数目 y = ，( 工) 圳，( 工) = x 4 + 口。工2 + a g x + a 。：，其中( f ) = 0 】， i v i = 9 2 海南帅甄大学坝士学位论又 a = ，( z ) i 厂( 工) = - a ) 2 ( 工2 + 2 锨+ 矽，口，】， 召= ，( x ) l ，( x ) = ( 石2 - t ) 2 , ( 工2 一丁) 在【工】内不可约】。 对于情形a ：定义一个映射： 9 ：f ；- - - - ) v 缈( 口，历= ( x - a ) 2 ( 工2 + 2 口x + 矽。 假设存在重根口磊，且缈( 口，) = 面，万) ，使得，( x ) = 7 ( x ) ，即当 ，( x ) = ( 工一口) 2 ( x 2 + 2 c r x + 矽， 7 ( 戈) = ( 戈一否) 2 ( z 2 + 2 赢+ 万) ， 那么 厂( 工) = 7 ( x ) = ( x 一口) 2 ( 工一夏) 2 。 此时还必满足 。 口：- - 0 ， 所以 怍鸟2 一下( q - 1 ) 。 而对于情形丑，由薮论 6 5 的知识，素域上的二次非剩余个数为鱼。 所以 f v t = l a l + l s i - q 2 。 3 2 2p i c a r d 曲线的同构类 令日是上c 勉厂( ) 2 ，3 的p i c a r d 曲线y 3 = 工4 + a 6 x 2 + a g x + a _ 1 2 的集合， h 。= h h a 。= a 9 = o ，0 1 2 o 】， h 3 = h h i a 。= q 2 = o ，口，o ) ， h ：= h ha 9 = o ，a 6 ，q ：都不为o ) ， h l = hi ( h 2u h 3 u h 4 ) 。 下面问题转化为求日，的方程个数， 1 4 第三章有限域上p i c a r d 曲线的同构类 - - - l _ _ - - - _ _ _ l l _ l _ _ _ _ _ l _ _ _ _ _ _ _ _ _ _ _ l - _ _ _ _ _ - - _ _ i _ - _ _ - _ - _ - - _ _ 一1 1 i _ 一 ( 1 ) a 4 f ( x ) eh 4 ，则，( 工) = z 4 + 口。2 ，其是奇异方程当且仅当q ：= o ，l = q - 1 。 ( 2 ) 令，( 工) h 3 ，贝l j f ( x ) = x 4 + a g x ，其是奇异方程当且仅当呜= o ，所以1 日3 i - q - 1 。 ( 3 ) 令f ( x ) e 日2 ，则，( 工) = 工4 + a 6 x 2 + 口1 2 ，其判别式( 通过m a t l a b 求结式的方法( 程 序1 ) 6 6 ) 方程是奇异的当且仅当 ( ，) = 1 6 a 1 2 ( a 6 2 4 口1 2 ) 2 ， a 6 2 = 4 q 2 ， l h 2 l = ( 口一1 ) 2 - ( q - 1 ) = ( 9 1 ) ( 9 2 ) 。 程序1 ： s y m sa _ 6a _ 1 2 a = 1 ，0 ，a _ 6 ，0 ，a _ 1 2 ，0 ，o ： 0 ，1 ，0 ，a _ 6 ，0 ，a _ 1 2 ，0 ； 0 ，0 ，1 ，0 ，a6 ，0 ，a _ 1 2 ： 4 ，0 ，2 , a _ 6 ，0 ，0 ，0 ，0 ： 0 ，4 ，0 ，2 a _ 6 ，0 ，0 ，0 ： 0 ，0 ，4 ，0 ，2 a _ 6 ，0 ，0 ： 0 ，0 ，0 ，4 ，0 ，2 a _ 6 ，0 ： d e t ( a ) a n s2 1 6 * a _ 1 2 * a _ 6 4 1 2 8 a _ 1 2 2 a _ 6 2 + 2 5 6 a _ 1 2 3 f a c t o r ( a n s ) a n s2 1 6 a _ 1 2 ( 一4 * a _ 1 2 + a _ 6 6 2 ) 2 ( 5 ) 躲j l i h 。i = q 3 - q 2 - 2 ( q 一1 ) 一( 鸟一1 ) ( 口一2 ) 若g 是 ( 工，) ，) _ ( 矿工，a 4 y ) ，口+ ( 3 2 1 ) 的变换群g 是属于日，类中的曲线的自同构群其中f - 1 ，2 ，3 ，4 ，由( 3 2 1 ) 得到 1 5 海南师范大学硕士学位论文 g f = 口巧p _ - q ， 且 所以日中同构类数目： i g l = g c d ( 3 i ，q - 1 ) 。 h g i - e i - ，g l = 古川lg f i = i g 。i + i g , i + s y m sa _ 8a _ 1 6 b = 【1 ，0 ，0 ，0 ，a _ 8 ，0 ，0 ，0 ，a _ _ 16 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，o ； o ，1 ，o ，o ，0 ，a _ 8 ，0 ，0 ，0 ，a _ 16 ，0 ，0 ，0 ，0 ，0 ，0 ，o ； o ，o ，1 ，o ，o ，0 ，a _ 8 ，0 ，0 ，0 ，a _ _ 1 6 ，0 ，0 ，0 ，0 ，0 ，o ； o ，o o ，1 ，o ，o ，0 ，a _ 8 ，0 ，0 ，0 ，a _ 1 6 ，0 ，0 ，0 ，0 ，o ； o ，o ，o ，o ，1 ，0 ，0 ，0 ，a _ 8 ，0 ，0 ，0 ，a _ 16 ，0 ，0 ，0 ，o ； o ，o ，o 0 ，o ，1 ，o ，o ，0 ，a _ 8 ，0 ，0 ，0 ，a _ 16 ，0 ，0 ，0 ； o ，o ，o ，o ，0 ，0 ，l ，o ，o ，0 ，a _ 8