（计算机应用技术专业论文）超椭圆曲线公钥加密与签名的研究.pdf

摘要 伴随信息技术的不断发展与电子商务、电子政务的不断推进，社会对计算机 和网络系统的依赖越来越大。确保计算机和网络系统的安全已成为计算机科学研 究中的热点领域。公钥密码体制是保障信息安全的关键技术，在数据保密和数字 签名方面发挥着重要的作用。 一 椭圆曲线密码体制是当今流行的公钥密码体制之一，被广泛地应用到军事、 经济、科技、生活等各个领域。超椭圆曲线密码体制是椭圆曲线密码体制的推广， 在安全性方面具有明显的优势。与现有的密码体制相比，同等安全约束下，超椭 圆曲线密码体制所需要的位数明显小于r s a 和椭圆曲线密码体制。 ， 目前，对于超椭圆曲线密码体制的研究还处于理论阶段。本文以超椭圆曲线 j a c o b i a n 群为理论基础，对超椭圆曲线上的数据保密以及数字签名算法进行了深 入研究。作者主要做了以下几个方面的工作： 通过程序代码实现了超椭圆曲线j a c o b i a n 群上的代数系统的基本运算，并 描述了系统参数的生成算法； 在原始超椭圆曲线e 1 g a m a l 公钥加密算法的基础上，结合e c i e s 与p e s c 算法的思想，分别提出了两种更安全的基于超椭圆曲线密码体制的数据加密算 法： 在原始超椭圆曲线d i f f i e h e l l m a n 密钥建立算法的基础上，结合s t s 与 e c q m v 算法的思想，提出了两种更安全的基于超椭圆曲线密码体制的密钥建立 算法； 通过超椭圆曲线数字签名公式的推导，提出了一种超椭圆曲线上的盲签名 算法； 通过超椭圆曲线数字签名公式的推导，提出了一种超椭圆曲线上的代理签 名算法。 关键词超椭圆曲线；j a c o b i a n 群；加密；密钥建立；数字签名 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to f i n f o r m a t i o nt e c h n o l o g ya n dt h ea d v a n c e m e n to f e - b u s s i n e s s a n de - g o v e r n m e n t , t h ec o m m u n i t i e sd e p e n do l lc o m p u t e r sa n dn e t w o r ks y s t e m sm o r ea n dm o r e t h em e t h o df o re n s u r i n gt h es e c u r i t yo f c o m p u t e r sa n dn e t w o r ks y s t e m sh a sb e c o m et h eh o t s p o t i nc o m p u t e rs c i e n c ea r e a p u b l i c - k e yc r y p t o s y s t e mi so n eo ft h em o s ti m p o r t a n tt e c h n o l o g i e st o g u a r a n t e e i n f o r m a t i o ns e c u r i t ya n dp l a y sa ni n d i s p e n s a b l er o l ei nd a t a - e n c r y p t i o na n d d i 百t a l s i g n a t u r e e l l i p t i cc u r v ec r y p t o s y s t e mi so n eo f t h em o s tp o p u l a rc r y p t o s y s t e m sa n dh a sb e e na p p l i e d w i d e l yo nm a n y a r e a si n c l u d i n gm i l i t a r y , e c o n o m y , s c i e n c ea n dp e r s o n a ll i f e h y p e r e l l i p t i cc h i v e c r y p t o s y s t e m i san a t u r a l g e n e r a l i z a t i o n o f e l l i p t i c m l l v e c r y p t o s y s t e m a n dw o r k s s u p e r e x e e l l e n t l yo ns e c u r i t ya s p e c t a tt h es a m es e c u r i t yl e v e l ，h y p e r e l l i p t i cc u r v ee r y p t o s y s t e m r e q u i r e sas m a l l e rb a s i sf i e l dt h a nr s a a n de l l i p t i cc u w ec r y p t o s y s t e m a tp r e s e n t ，t h es t u d yo fh y p e r e l l i p t i cc u l w ec r y p t o s y s t e mi ss t i l li nt h es t a g eo ft h e o r e t i c a l r e s e a r c h t h ed i s s e r t a t i o nm a k e sad e e pr e s e a r c ho nd a t a - e n e r y p t i o na n dd i g i t a l - s i g n a t u r eb a s e d o nh y p e r e l l i p t i cc u r v ej a c o b i a n t h em a i nw o r ki nt h i sd i s s e r t a t i o ni sa sf o l l o w s 1 1 1 r o u g hp r o c e d u r a lc o d e ，h y p e r e l l i p t i cc u l w ej a c o b i a na l g e b r a i cs y s t e mi si m p l e m e n t e d o nc o m p u t e ra n dt h ea l g o r i t h m so f p a r a m e t e r sg e n e r a t i n ga r ed e s c r i b e d o nt h eb a s i so fo r i g i n a lh y p e r e l l i p t i cc u r v ee 1 g a m a lp u b l i c - k e ye n c r y p t i o na l g o r i t h m c o m b i n i n gw i 山e c i e s a n dp e s ca l g o r i t h m t w od a t a - e n c r y p t i o na l g o r i t h m sw i t hm o r es e c u r i t y b a s e do nh y p e r e l l i p t i ec u r v ee r y p t o s y s t e mi sp r o p o s e d o nt h eb a s i so fo r i g i n a lh y p e r e l l i p t i cc u r v ed i f f i e - h e l l m a nk e y - e x c h a n g ea l g o r i t h m c o m b i n i n gw j t hs t sa n de c q m va l g o r i t h m t w ok e y - e x c h a n g ea l g o r i t h m sw i i hm o r es e c u r i t y b a s e do i lh y p e r e l l i p t i cc u l w ec r y p t o s y s t e mi sp r o p o s e d t h eh y p e r e l l i p t i cc u r v ed i g i t a ls i g n a t u r ef o r m u l ai s d e r i v e da n dab l i n ds i g n a t u r e a l g o r i t h mb a s e do nh y p e r e l l i p t i cc o r v ec r y p t o s y s t e mi sp r e s e n t e d ； t h eh y p e r e l l i p t i cc u r v ed i g i t a ls i g n a t u r ef o r m u l ai sd e r i v e da n dap r o x ys i g n a t u r e a l g o r i t h mb a s e d o l lh y p e r e l l i p t i cc u r v ec r y p t o s y s t e mi sp r e s e n t e d 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 ；j a c o b i a n ；e n c r y p t i o n ；k e y - e x c h a n g e ；d i g i t a ls i g n a t u r e 1 1 i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示了谢意。 獭：垃吼盟剑 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容， 可以采用影印、缩印或其他复制手段1 呆存论文。 ( 保密的论文在解密后应遵守此规定) 戳：拯导臌日期：毫竺1 2 1 垒 1 1 研究背景与意义 第1 章绪论 密码学是一门既古老又新奇的科学，它是以研究秘密通信为目的，在编码 与破译的斗争实践中逐步发展起来的，随着先进科学技术的应用，密码技术己 成为一种综合性的尖端科学。伴随信息技术的不断发展与电子商务、电子政务 的不断推进，密码学在社会生活中扮演着越来越重要的角色。- 现代密码学形成于二十世纪七十年代，它的理论基础首推1 9 4 9 年s h a n n o n 的一篇文章保密通信的信息理论。在现代密码学上有两件大事：第一件事是 1 9 7 7 年美国国家标准局正式公布实施了美国的数据加密标准d e s ，并批准将其 用于非机密单位及商业上的保密通信，从而标志了对称密码数据加密标准的形 成，密码学的神秘面纱从此被揭开；第二件事是w d i f f i e 和m h e l l m a a 联合发 表的论文密码学的新方向【l 】，提出了适应网络上保密通信的公钥密码思想， 揭开了公钥密码研究的序幕。这两件密码学界的大事分别代表了目前学上的两 种密码体系：传统密码和公钥密码，或分别称为对称密码体制和非对称密码体 制。 传统密码只是提供了数据的保密性，不能保证数据的认证性和完整性；公 钥密码不但能够用于提供数据的保密传输，而且还可以方便地实现诸如密钥的 建立、数字签名、密钥的分发以及身份认证等功能。 现有的公钥密码体制均以数学难解问题作为基础，基于以下数学难解问题 所构造的公钥密码体制被认为是安全有效的： 基于大整数分解问题( i n t e g e rf a c t o r i z a f i o np r o b l e m ，i f p ) 的公钥密码体 制； 基于有限域上离散对数问题( d i s c r e t el o g a r i t h mp r o b l e m ，d l p ) 的公钥 密码体制； 基于椭圆曲线离散对数问题( e l l i p t i cc u r v e d i s c r e t el o g a r i t h mp r o b l e m ， e c d l p ) 的公钥密码体制。 近几年来，人们对前两类问题的求解能力有了很大的提高。5 1 2 位的r s a 算法在1 9 9 9 年就己经被攻破，而求解d l p 的i n d e x - c a l c u l u s 方法也已经达到亚 指数阶。为保障这两类密码系统的安全，目前我们不得不采用1 0 2 4 比特甚至 2 0 4 8 比特大小的密钥。而且随着计算能力的进一步提高，可以被分解的大整数 和可以被解决的离散对数问题的位数还会不断提高，从而导致必须采用越来越 长的密钥，以及由于密钥的增长所带来的种种问题，如加密解密计算的复杂性 北京丁业人学丁学硕i 学位论文 的提高，存储和传输密钥需要的资源的增加等，都将限制两类密码系统的应用。 并且整数分解和离散对数问题在本质上是一致的，如此狭窄的数学背景也不得 不令人担忧。综上所述，继续开发和研究新的密码算法势在必行。 1 2 研究现状 在至今为止的所有公钥密码中，最著名的是由r r i v e s t 、a h a m i r 和 l a d l e m a n 三位教授于1 9 7 7 年提出的r s a 公钥密码体制【z 】。r s a 所具有的安 全性基于数论的一个原理：将两个大的素数合成一个大数很容易，相反的，将 这个大数分解为两个素因子的过程则非常困难。由此可见，r s a 的安全性依赖 于作为公钥的大数n 的分解的难度。 有限域上的椭圆曲线密码体锖j j ( e c c ，e l l i p t i cc u r v ec r y p t o s y s t e m ) 3 】【4 】是8 0 年代美国华盛顿大学的n k o b l i t z 教授和当时在i b m 工作的v m i l l e r 教授相互 独立地提出的。椭圆曲线密码体制的数学基础是利用椭圆曲线上的点构成的 a b e l i a n 加法群中离散对数的计算困难性。从己有的攻击算法表明【5 】：有限域上 的椭圆曲线加法群离散对数问题( e c d l p ) 的困难性要高于一般乘法群上的离 散对数问题。在相同加密强度的条件下，e c c 所需要的密钥长度比r s a 更短， 因此更利于嵌入式系统的应用。作为e c c 的一个推广，n k o b l i t z 在1 9 8 9 年提 出了超椭圆曲线密码体制( h e c c ，h y p e r e l l i p t i cc u r v ec r y p t o s y s t e m ) ，它的基 础是有限域上超椭圆曲线的j a c o b i a n 群上的离散对数问题的计算困难性 ( h c d l p ) 。与椭圆曲线( e c c ) 和r s a 公钥密码体制相比，超椭圆曲线密码体 制( h e c c ) 更具有以下优点： 比较建立在相同有限域上的h e c c 及e c c ，h e c c 比e c c 有更高的安 全强度。h e c c 的安全性主要依赖于h c d l p 的安全性，从现有对h c d l p 的攻 击来看，对于低亏格( g 4 ) 的h c d l p 还没有发现有什么特别大的弱点，除了 极少特殊的情况外，求解时间都是完全指数时间。因而建立在低亏格h c d l p 上的超椭圆曲线密码体制被认为是安全的； 在与r s a 或传统离散对数密码系统相同的安全强度下，超椭圆曲线密码 体制可以选用更短的操作数，更小的带宽。在实际中，操作数长度在5 0 - 8 0 位 之间所建立起的密码体制就足以抗击目前己知的攻击。这使得在6 4 位处理器上 实现有限域元素的高速单次运算成为可能，从而避免了多次复合计算的整数运 算中可能产生的错误，便于存储和运算的实现； 在同等安全水平下，超椭圆曲线密码要比椭圆曲线密码所用的基域小， 且h e c c 可以模拟一般乘法群上如d s a ，e l g a m a l 等几乎所有的协议： 在同样的定义域上，亏格越大曲线越多，可用于构建密码体制的安全曲 第l 章绪论 线的数目也就越多，即对于固定位宽数据长度的芯片，通过对超椭圆曲线密码 算法参数的修改，就可以轻松地构造出更加安全的密码体制； 超椭圆曲线密码是e c c 的一个推广，所以用于椭圆曲线密码体制上的一 些普遍的技术和方法通常也可以应用在超椭圆曲线密码体制上，从而对目前已 经走向实用化的超椭圆曲线密码体制无论在理论上还是在实现上都有益处。 当前国外已有许多关于超椭圆曲线密码体制的研究成果和软硬件实现的 论文：h p 实验室的n p s m a a t 6 j 利用m i c r o s o f ty i s u a lc + + 最先实现了g 只2 m ) 域上超椭圆曲线数字签名算法( h c d s a ) ，日本的ys a k a i 等【1 【8 】使用a l p a h 计 算机实现了超椭圆曲线密码算法；t w o l l i n g e r 9 】在其硕士论文中提出了超椭圆 曲线密码体制硬件实现的架构和v h d l 描述；美国路易斯维尔大学的d a w i l l i a m s t lo 】在其硕士论文中描述超椭圆曲线算法类库的实现；美国伊利诺斯大 学香槟分校的t c c l a n e y 1 1 】在其硕士论文中研究了g f ( 2 m ) 域上亏格为2 的超 椭圆曲线密码系统在f p g a 上的实现。 目前，国外对于h e c c 的研究已经非常热门，反观国内这方面的研究还 不多。虽然超椭圆曲线密码实现的复杂度较大、加密时问较长，但是m r o s i n g 和n bs m a r t 在其著作中对超椭圆曲线密码给出了很高的评价。相信经过努 力，超椭圆曲线公钥密码体制会逐渐进入到主流的密码学应用当中。 1 3 论文的结构与内容 第1 章是绪论，介绍了课题的研究背景、研究现状、论文的结构与内容。 第2 章是超椭圆曲线公钥密码体制的基础知识。主要介绍了与超椭圆曲线 密码相关的数学背景知识，如有限域上超椭圆曲线的定义，除子的定义及性质， 超椭圆曲线的j a e o b i a n 群和超椭圆曲线离散对数问题的定义等。 第3 章是超椭圆曲线密码体制的代数实现。本章首先论述了实现超椭圆曲 线公钥密码体制的各种算法，即有限域上的数学运算、建立在有限域上的多项 式的运算以及基于多项式的超椭圆曲线密码体制运算；然后论述了密码系统的 参数设置问题，包括超椭圆曲线曲线阶的计算以及曲线基点的生成问题。 第4 章超椭圆曲线上的数据保密算法，主要论述超椭圆曲线公钥密码体制 在数据保密传输方面的应用。本章在简要描述了现有的两类基本的数据保密算 法，即d i f l i e - h e l l m a n 密钥协商算法以及e l g a m a l 公钥加密算法之后，分别提 出了在超椭圆曲线上实现上述两种算法的算法，然后，针对这两种算法各自特 点，分别提出了两种改进算法，并具体的给出了两种算法描述。 第5 章是超椭圆曲线上的数字签名算法，主要论述超椭圆曲线公钥密码体 制在数字签名算法的应用。本章在简要描述了现有的几种数字签名算法以及广 北京i 业人学t 学硕t 学位论文 义的数字签名算法之后，给出了将现有数字签名算法平移到超椭圆曲线公钥密 码体制上的实现算法。在实现了超椭圆曲线在数字签名方面的基本应用之后， 论文进一步论述了超椭圆曲线公钥密码体制在盲签名与代理签名这两种特殊数 字签名中的应用，并分别提出了基于超椭圆曲线的盲签名和代理签名算法。 最后是本文的结论，对全文进行了总结，说明了本文的所做的工作，并提 出了进一步的研究方向。 第2 章超椭圆曲线密码学摹奉概念 第2 章超椭圆曲线密码学基本概念 超椭圆曲线是一类特殊的代数曲线，被视为椭圆曲线的推广。亏格等于l 的超椭圆曲线就是椭圆曲线。通过在超椭圆曲线上定义除子的等价类，可以构 造超椭圆曲线j a c o b i _ a n 群元素及运算，从而实现超椭圆曲线上的公钥密码算法。 本章中关于h e c c 的大部分内容取自 1 2 ，代数几何方面的相关知识可参考文 献【1 3 】【l4 】【1 5 】，关于本章中涉及的定理证明细节见文献 1 2 】【l4 】 1 6 】。 2 1 基本定义 定义2 1 设f 为数域，f 为，的代数闭包。定义在，上的超椭圆曲线方 程为： c ：1 ，2 + h ( u ) v = f ( u ) 如，v ) f u ，川( 2 1 ) 其中 ( “) 为次数最多为g 的多项式( 其中亏格g - d ，而贝“) 为次数为2 矿l 的首一多项式，且超椭圆曲线c 上的点集 ( ，v ) i ”，v f 中不存在奇异点。 曲线c 上的奇异点定义为同时满足以下三个方程的坐标( “， ，) 尹f ： l v 2 + j i l ) ，= f ( u ) 2 v + i l ) = 0 lj i l ( 甜) v - f 。( “) = 0 定理2 1 令c 为定义在有限域f 上的超椭圆曲线， c ：v 2 + h ( u ) v = ，( “) ( 甜，v ) f l u ，v 】，有： 若 ( “) = o ，则需保证c h a r ( 1 搿2 。 ( 2 - 2 ) 即对于曲线 若e h a r ( f ) 2 ，则通过如下变换“斗甜，v 斗( v - h ( u ) 2 ) ，从而将等式 ，2 + | | ( 甜) v = f ( u ) 变换为v 2 = f ( u ) ，其中的次数为2 9 + i 。 令c 为定义在有限域f 上的代数曲线，其中 ( “产0 且c h a r ( f ) 2 ，则c 为超椭圆曲线当且仅当贝“) 在f 上没有重根。 定义2 - 2 令k 为域f 的扩域。设域k 上符合超椭圆曲线定义式c 有理点 集为c ( 目。c ( 回为满足代数曲线v 2 + h ( u ) v = f ( u ) 的点集p = ( x , y ) ( k x k ) 和 无限点( 写作o o ) 的并集。除0 0 外，c ( 目中所有的点均称为有限点。 ，e 北京丁业大学t 学硕i j 学位论文 定义2 - 3 令p = ( 工，y ) 为超椭圆曲线c 上的有限点。p 的逆元定义为 声= ( - x ，一y 一_ j l ( 功) ( 声必然在曲线c 上) ；对于无限点，其逆元定义为品：m 。 若一个有限点p 满足p = 声，则称该点为特殊点；否则，该点称为普通点。 例2 1 设c z ：v 2 = 5 5 u 3 + 4 u = u ( u i x u + 1 ) 一2 ) + 2 ) ，在实数域平 面坐标系上形成的图像为： 厂八 v u 图2 - 1 函数v 2 = u 5 5 u 3 + 4 u 的图象 f i g u r e 2 1i m a g e o f f u n c t i o nv 2 = “5 5 u 3 + 缸 例2 - 2 有限域，= 卅“工5 + 工2 + 1 ) 上，设口为有限域，的原根，c 3 上 的有理点集c ( t ，) 为： ( o ，1 ) ( ，5 ) ( 4 ，) ( 一8 ，a 2 9 ) ( 3 ，0 ) ( 7 ，) ( o ，o ) ( 1 ，1 ) ( a 9 ，孑7 ) ( 一4 ，一9 ) ( 9 ，) ( 3 ，) ( 孑8 ，) ( o ，一6 ) ( ，5 ) ( 矿，两 ( 5 ，o ) ( 一9 ，8 ) ( 5 ，叻 ( 8 ，6 ) 2 2 多项式函数与有理函数 ( ，孑7 ) ( o ，3 ) ( 5 ，) ( o ，一5 ) ( 矿，4 ) ( 9 ，o ) ( ，西 ( o ，o ) ( 8 ，彭3 ) ( o ，9 ) ( a 2 7 , o ) ( 9 ， 定义2 - 4 有限域f 上基于曲线c 的多项式环，用符号研c 】表示。在多项 式环f 【c 】= f u ，v ( v 2 + h ( u ) v 一厂( “) ) 中，多项式v 2 + ( “) v 一厂o ) 为以“，v 为 第2 章超椭圆曲线密码学肇奉概念 自变量的多项式集合研“，v 】上的理想。类似地，曲线c 在代数闭域f 上的定义 为：冗c 】_ p u ，v ( v 2 + h ( u ) v 一，似) ) ，夙c 】上的元素称为曲线c 上的多项式 函数。 定理2 - 2 多项式，0 ，d = ，2 + | i ) v 一0 ) 为f 上的不可约多项式，且 冠c 】为一整环。 定义2 5 令g ( u ，d = 口 ) 一b ( u ) v 为冠c 】上的多项式函数，定义g ( 甜，y ) 的 逆变换为虿似，d = 口o ) + 6 ) ( ) + v ) 。 定义2 - 6 令g ( u ，v ) = 口( “) 一b ( u ) v 为冗c 】上的多项式函数，定义g 的模为 ( 6 3 = g 虿。 通过对模函数的定义，从而将含有两个自变量的多项式函数转换为仅具有 一个自变量的多项式，从而使问题得到简化。 定理2 3 令g ，h e 研c 】为多项式函数，则 ( g ) 为一个p u 】上的多项式； ( 面= ( g ) ； n ( g h ) = ( g ) ( h ) 。 定义2 7 将f ( c ) 定义为域f 上由，【c 】中元素构成的分数。类似地，将 户( c ) 定义为域f 上由冗c l 中元素构成的分数。f ( c ) 上的元素称为曲线c 上 的有理函数。 定义2 8 令r = g h 风c ) ，且令p c ，p o o 。若p 在有理函数上有 ，j 定义，即g ，h 研c 】且日( p ) 0 ，则称r 定义在点p 上；若在飞上不存在这 样的g ，日冠c 】，则称r 在点p 上无定义。若r 定义在p 上，则r 在p 点的 值定义为r ( p ) = g ( p ) h ( p ) 。 定义2 - 9 令g ( “，= 口0 ) 一b ( u ) ；k j 冗c 】上的非零多项式。其中，g 的度定 义为： 北京t 业人学t 学硕l 学位论文 d e g ( g ) = m a x 2 d e g 。( 4 ) ，2 9 + 1 + 2 d e g 。( 6 ) )( 2 - 3 ) 定理2 - 4 令g ，h 研c 】，则 o d e g ( g ) = d e g 。( ( g ) ) ； d e g ( g h ) = d e g ( c ) + d e g ( h ) ： d e 颤g ) = d e g ( g ) 。 定义2 l o 令r = g h f ( c ) 为一个有理函数，则： 若d e g ( g ) d e g ( h ) 则称r 在点o o 上无定义； 若d e g ( g ) = d e g ( h ) 则r 在点。o 的值为多项式g 与h 首项系数的比值。 2 3 零点与极点 定义2 1 l 令r = g h p ( c ) 为一非零有理函数，且令p c 。若 r ( p ) = 0 ，则称r 在p 上为零点。若r 在p 上无定义，则称r 在p 上为极点， 写作r ( p ) = m 。 定理2 - 5 令g 冗q 为非零的多项式函数，r - 令p e c 。若g ( p ) = 0 ，则 矾声) = 0 。 定理 2 - 6 令p = ( 工，y ) 为曲线c 上的点。设非零多项式 g ( u ，y ) = 口 ) 一b ( u ) v 冗c 】在p 上为零点，且p 的横坐标z 不是a ( u ) - - 与6 ( 的 根，则有g ( p ) = 0 当且仅当p 为特殊点。 定理2 7 令p = ( 工，y ) 为曲线c 上的普通点，g ( u ，v ) = 口( “) 一b ( u ) v f 【c 】， g ( p ) = 0 且j 不是口( “) 与6 ( “) 的根。可以将g 写为似一工) 5 s 的形式，其中s 为 ( u - - x ) 除( g ) 的最高次幂，s f ( c ) 在p 点既非零点也非极点。 定理2 8 令p = o ，y ) 为曲线c 上的特殊点。0 工) 可以写作 ( v - - y ) 2 s ( u ，v ) 的形式。其中s 承c ) 在p 点既非零点也非极点。 定理2 - 9 令尸c 。对于在p 点上的有理函数u f ( c ) ，当c 厂( d = o 时， 对任意非零多项式6 ( u ，v ) = d 似) 一地p 冠q ，存在整数d 及有理函数 s f ( c ) ( s ( 户) 0 ，0 0 ) ，使g = u 4 s 。其中，整数d 的取值不依赖于对【，的 选择，函数u 称为p 点上的归一化参数。 定义2 1 2 令g ( u ，v ) = 口( “) 一b ( u ) w 冗c 】为非零多项式函数，p c c ， u f ( o 为p 上的归一化参数，有g = u 4 s ，其中s f ( o ( s ( p ) o ，o o ) 。 从而将g 在p 点的阶定义为o r , p ( g ) = d 。 定理2 1 0 令g 。，g 2 研c 】为非零多项式，p e c ，设o r , ，( g 1 ) = ， o r d ，( g 2 ) = r 2 ，则有： o r d ，( g i g 2 ) = o r d p ( g 1 ) + o r d ，( g 2 ) ； 若，2 ，贝i o r a p ( g j + g 2 ) = m i n ( ，r z ) ； 若= 吒，g t - g z ，则o r d p ( g l + g 2 ) r 2 。 定义2 1 3 令g ( u ，v ) = 4 ( “) 一b ( u ) v 冗c 】为非零多项式，p c 。o r d p ( g ) 即g 在p 点的阶定义如下： 若p = ( x , y ) 为有限点。令，为0 一曲同时除口( 帕，6 ( “) 的最高次幂，有 g ( u ，v ) = ( 一曲7 ( 口o ( “) 一6 ( “) o v ) 。 若( 力- b ( x ) o y 0 ，则令删：否则，若a o ( 工) 一m 算) o y = 0 ，令j 为一力 n ( a o ( ) 一6 ( “) o v ) = a 0 2 + 口0 6 0 一6 0 2 ，的最高次幂。 若p 为普通点，则o r d p ( g ) = r + s ； 若p 为特殊点，$ l j o r d p ( g ) = 2 r + s 。 若p = 0 0 ，则o r d p ( g ) = m a x 2 d e g 。0 ) ，2 9 + l + 2 d e g 。( 6 ) ) 北京丁业人学t 学硕i 学位论文 定理2 - 1 1 定义2 - 1 2 与定义2 - 1 3 等价。将定义3 - 1 3 定义的函数写作丽， 则对曲线上的任意点p c 与非零多项式g 冗c 】，有d 耐，( g ) = o r , ，( g ) 。 定理2 - 1 2 令g e 冠c 】为非零多项式函数，p c c ，有口趔，( g ) = o r d ，( 石) 。 定理2 - 1 3 令g 冠c 】为非零多项式函数，则g 上仅有有限个零点与极点， 且o r d ，( g ) = 0 。 p e c 定义2 1 4 令r = g h 声( c ) 为非零有理函数，p e c ，则r 在p 点的阶 o r a p ( 月) = o r d p ( g 卜o r j p ( h ) e 2 4 超椭圆曲线上的除子 定义2 1 5 一个除子d 为曲线c 上点的一个形式和，即 d = m p p ，m p z 在除子形式和的每一项中，仅有有限个m ，非零。除子d 的度 d e g d = e m ，p 。除子d 在p a 的阶o , d p ( d ) = m ，。 曲线c 上的所有的除子加法规则( 式2 - 3 ) 下构成一个群，写作d 。 m ，p + 甩，p = ( 研，+ n p ) 尸 ( 2 _ 3 ) p e c p e cp e c 所有度为零的除子构成的集合为除子集d 的子群，写作d o 。 定义2 - 1 5 令除子d j = 研，p ，d 2 = 唧p 。d - 与d 2 的最大公约除予定 f e c p , e c 义为： g c d ( d i ，d 2 ) = m i n ( m p ，胛，) p + ( m i n ( 珊p ，n p ) ) o o d 。( 2 - 4 ) e c c 定义2 - 1 7 设re 尹( c ) 为非零有理函数。r 上的除子定义为： d i v ( r ) = ( o r d ，r ) e ( 2 5 ) 对于r = g h y ( c ) ，有d i v ( r = d i v ( g ) - d i v ( h ) ； 对于r = r i r 2 f ( o ，d i v ( r l 如) = d i v ( r 1 ) + d i v ( r 2 ) - 例2 - 3 对于曲线c 上的除子d i v ( u x ) ，有： 若p = ( x ，y ) 为曲线c 上的普通点，d i v ( u 一曲；p + 声一2 0 0 ； 若p = o ，y ) 为曲线c 上的特殊点，d i v ( u 一曲= 2 p - 2 0 0 。 定理2 - 1 4 设g ( u ，v ) 冠c l 为曲线c 上的非零多项式函数，令 d i v ( g ) = ，f ，尸，则咖( 西= 肌，。 p e cp e c 定义2 1 8 令除子d e d o ，有理函数月履c ) ，设d = a i v ( r ) ，则称除子 d 为主除子；所有的主除子构成的集合，写作p ，主除子集p 为d o 的子集；通 过主除子在上构造可交换群：商群，= d o p 称为曲线c 上的j a c o b i a n 群； 设d l ，d 2 d o ，若d l d 2e p ，则称d l ，d 2 等价，写作d l d 2 。 定义 2 - 1 9 令除子d = 班，p ， 则除子d 的支撑集 ，e c s u p p ( d ) = p c l m p o 定义2 - 2 0 对于形如d = m ，e - ( m 。p 的除子，若满足以下条件： 任取l ，有朋。 0 ， 若马为普通点，且只6s u p p ( d ) ，则有耷仨s u p p ( d ) ， 若尸f 为特殊点，则州，= l ， 则称除子d 为半规约除子。 定理2 - 1 5 对任意除子d d o ，存在半规约除子d l d 。与d 等价d l d 。 2 5 半规约除子 定理2 - 1 6 令p = j ，) 为曲线c 上的普通点，有理函数r f ( o 在p 处非 极点。对任意k 0 存在唯一的c 。，q ，幺f 与r 。f ( c ) ，有 t r = c j o 一曲+ ( u - - x ) “1 心。其中，鲰在p 处非极点。 定理2 1 7 令p = “，y ) 为曲线c 上的普通点，任取k i ，存在唯一的多项 北京t 业人学t 学硕f ：学位论文 k b a u ) 冗c 1 满足： d e g 。b k 七； 以( 力= y ； 巩2 ) + b a u ) h ( u ) ；f ( u ) ( m o d ( u - x ) ) 。 定理2 - 1 8 设d = 朋，只一( m ，) o o 为半规约除子，设只= ( 一，咒) 。令 口似) ；h 似- - x 。) ”，则存在唯一的多项式6 ( ) 满足： d e g 。b d e g 。a ： 对于所有系数m r 不为零的项，b ( x ，) = y ，； ( “) i6 2 ( “) + b ( “) ( “) 一f ( u ) 。 可将除子d 改写为最大公约除子表示形式： d = g c d ( 讲v ( 口( “) ) ，d i v ( b ( u ) 一v ) ) ( 2 - 6 ) 最大公约除子表示形式