（基础数学专业论文）椭圆曲线与实二次函数域的dlp等价.pdf

四川大学硕七学位论文 y9 9 4 9 7 3 椭圆曲线与实二次函数域的d l p 等价 基础数学 研究生王佳昱指导老师彭国华 继r s a 之后，椭圆曲线的密码体制成为公钥密码体制的热点，目前正越来 越广泛地应用于保密通信和数字签名。在椭圆曲线上建立密码体制主要依赖于 椭圆曲线上离散对数问题( e c d l p ) 的困难性。因此对e c d l p 的研究变得非 常重要。 另一方面，s c h e i d l e r ，s t e i n 和w i l l i a m s l 6 瞻用实二次函数域上理想类群的 离散对数问题建立了密钥交换体系。基于这种群的离散对数问题的困难性同样 可以用来建立e i g a m a l 签名方案。 事实上，椭圆曲线的离散对数问题与函数域上理想类群的离散对数问题存 在某种等价关系在特征不等于2 ，3 的情形，a n d r e a ss t e i n 1 l 建立了有限域上椭 圆曲线由一个有理点生成的群( 除去这个点本身) 与对应实二次函数域上的既 约主理想之间的一一对应，证明了这二者的离散对数问题等价r o b e r t j z u c c h e r a t o m i 讨论了当有限域的特征等于2 情形的类似问题。本文延用同样的 方法，借助连分数展开讨论了特征等于3 时，既约主理想与有理点群( 除去这 个点本身) 之间的一一对应，同样证明了它们的离散对数问题是等价的。由此 得到有限域上椭圆曲线的离散对数问题与相应实二次函数域上的既约主理想的 离散对数问题一样困难 关键词：椭圆曲线实二次函数域连分数离散对数问题( d l p ) 四川人学硕士学位论文 t h ee q u i v a l e n c eo fd i s c r e t el o g a r i t h m sb e t w e e ne l l i p t i cc u r v e a n dr e a lq u a d r a t i cf u n c t i o nf i e l d m a t h e m a t i c s p o s t g r a d u a t ew a n gj i a y u a d v i s o r p e n gg u o h u a t h ee l l i p t i cc u r v ec r y p t o g r a p h y ( e c c ) i sn o wt h eh o tp o i n ti n p u b l i ck e y c r y p m g r a p h ya f t e rr s 丸i tt h e nc a nb ea p p l i e di nm e s s a g es e c u r i t ya n dd i g i t a l s i g n a t u r e s t h es e c u r i t yo fe c cd e p e n d so nt h ed i f f i c u l t yo fd i s c r e t el o g a r i t h m s p r o b l e mf o re l l i p t i cc u r v e s ( e c d l p ) o v e rf i n i t ef i e l d s o nt h eo t h e rh a n d 。s c h e i d l e r , s t e i na n dw i l l i a m s l 6 l p r o p o s e dak e ye x c h a n g e p r o t o c o lw h i c hm a k e su s eo ft h ed i s c r e t el o g a r i t h m sp r o b l e mf o rr e a lq u a d r a t i c f u n c t i o nf i e l d s t h i si n f r a s t r u c t u r eo fq u a d r a t i cf u n c t i o nf i e l d sa l s oc a nb eu s e dt o i m p l e m e n te 1 g a m a lt y p es i g n a t u r es c h e m e s i nf a c t , t h ed i s c r e t el o g a r i t h m sp r o b l e mf o re l l i p t i cc u r v e so v e rf i n i t ef i e l d si s e q u i v a l e n tt ot h ed i s c r e t el o g a r i t h m sp r o b l e mf o rr e a lq u a d r a t i cf u n c t i o nf i e l d s i n 【1 】，a n d r e a ss t e i ne x p l i c i t l yg a v et h eo n e t o o n ec o r r e s p o n d e n c eb e t w e e nt h eg r o u p g e n e r a t e db yar a t i o n a lp o i n to fae l l i p t i cc u r v e ( w i t h o mt h ep o i n ti t s e l f ) o v e rf i n i t e f i e l d si nc h a r a c t e r i s t i cpq i sn o t2 3 ) a n dt h es e to fr e d u c e dp r i n c i p a li d e a l so ft h e c o r r e s p o n d i n gr e a lq u a d r a t i cf u n c t i o nf i e l d s , t h e nt h e i rd i s c r e t el o g a r i t h m sp r o b l e m s a r ee q u i v a l e n t i n 【4 1 ，r o b e f tj z u c c h e r a t os h o w e dt h es i m i l a rc a s eo v e rf i n r ef i e l d s i nc h a r a c t e r i s t i c2 i nt h i sp a p e r w es h o ws u c he q u i v a l e n c ea l s oe x i s t sw h e nt h e c h a r a c t e r i s t i co ff i n i t ef i e l d si s3 n em e t h o di sc o n t i n u e df r a c t i o n k e yw o r d s ：e l l i p t i cc u r v e ；r e a lq u a d r a t i cf u n c t i o nf i e l d s ；c o n t i n u e df r a c t i o n ；d l p 2 lii-厂ll0 11 0 四川大学顾士学位论文 引言 s h a n k s 3 1 1 9 7 2 年最先介绍了实二次函数域上理想类群的理想类之日j 存在 的内在结构关系。这种理想类群的结构关系随后被推广到函数域上。s c h e i d l e r ， s t e i n 和w i l l i a m s 6 i 应用函数域上的这种理想类群结构建立了密钥交换体系。后 来，这种群结构关系也用于建立e i g a m a l 签名方案。 问题是，利用实二次函数域建立密码体制，如何保证其安全性? 在公钥密码体制中，利用有限域上的椭圆曲线建立密码体制并证明其安全 性已经有了大量的工作。这主要依赖于椭圆曲线上离散对数问题( e c d l p ) 的 困难性。如果椭圆曲线上的离散对数问题与上文所提到的实二次函数域上的理 想类群结构有某种等价关系，则可以证明基于实二次函数域建立的密码体制的 安全性。 事实上，对实二次函数域上的既约主理想，我们可以定义其离散对数问题， 简称为实二次函数域的离散对数问题。s t e i n 1 】讨论了当有限域的特征不等于2 ，3 时，亏格为1 的实二次函数域上的既约主理想与对应椭圆曲线上由一个有理点 生成的群( 除去这个点本身) 之间的一一对应以及二者的离散对数问题等价。 而r o b e r tj z u c c h e r a t o 【4 时论了当有限域的特征等于2 时的情形。本文将就特征 等于3 时的情形，给出既约主理想与椭圆曲线的有理点生成的群( 除去这个点 本身) 之问精细的对应，并证明此时，实二次函数域与椭圆曲线的离散对 数问题等价。 在第一章中，我们介绍连分数推广到函数域上后具备的一些性质。然后， 在第二章，我们定义函数域上的既约理想，并运用连分数展开来考察所定义的 既约理想。另一方面，第三章把椭圆曲线进行分类，并就我们将要讨论的情形 给出椭圆曲线的双有理等价第四章是我们的主要结论和证明，精细的一一对 应图和离散对数问题的等价将在这章给出。 2 0o-，riili， lr，l，rlr 口l ，口：，口，6 1 ，b ：，b ，可以是实数或者复数，项数可以有限，也可以无限而 形如a i + 1 口2 + 1 口3 + - 的表达式称为简单连分数，简记为k ，口：，4 ，】。这里第 一项口。通常是正的或负的整数，也可以是零，项4 ：，a ，44 ，是正整数 连分数思想的最早期的线索比较模糊，许多古代的数学结果只是对这种分 数的一种启发。连分数的文献出现是在印度数学家a r y a b h a t a 的著作中，包含 了最早用连分数去求线性不定方程的一般解的一个尝试。大多数权威认为连分 数的近代理论开始于r a f a e lb o m b e l l i 。他的关于代数方面的论文在介绍平方根 时，指出西- 3 + 乞广而d a n i e is c h w e n t e r 在他的著作 g e o m e n r i c a 6 + 磊 p r a c t i c a 中用连分数发现了求磊1 7 7 i 的近似值的方法。另一个使用连分数的卓越 z j j 3 数学家是b r o u n c k e r ，他把! 转化成了连分数! 1 + j i 。后来，伟 石 石2 + 毒 2 + 大的荷兰数学家，力学家，天文学家和物理学家c h u y g e n s 为了给出天文馆齿 轮的正确设计一个好的近似使用了连分数。由此开始，象e u l e r , l a m b e r t ，l a g r a n g e 等大数学家发展了连分数理论。欧拉的主要论文 d ef r a c t i o n i b u sc o n t i n i u s ) 为连分数的现代理论奠定了基础。 对于简单连分数，我们在展开式的第1 1 层处切断，可以得到! 生一k ，4 。】， 吼 称为连分数的第n 个渐近分数。 运用渐近分数的性质进行逼近，我们可以用连分数来求平方根以及求对数 值。具体的方法可以在文 1 0 i f l l 1 1 d p 查阅连分数还有一个重要的运用，求解 丢番图方程式，也就是具有整数解( 有时是有理数解) 的不定方程，以及用于 求解佩尔方程式x 2 一y 2 - 1 。连分数的逼近理论表明每一个渐近分数都比前 一个渐近分数更接近于无穷简单连分数的值，并且收敛到一个已给的数。这样 连分数又有了几何的解释，推广为连分数的解析理论。在计算机普遍使用的今， 天，连分数常被用来绘制各种复杂函数的近似。 在对连分数的发展和应用中，其表达式中的项a ，也可由单纯的数推广为其 他的数学对象。在本文中，连分数的项就被推广为多项式。值得庆幸的足，这 样的推广仍然具备原始连分数的大部分性质，而这些性质对本文要证明的结果 起着关键性的作用。 1 2 二次函数域中的连分数展开 一个二次函数域k 是指有理函数域七一c o ) 的二次扩张。假设2 不整除叮， 即当是奇特征时，每个二次扩张都可以写成k 一0 ) + o ) 厕，其中 d o ) z 口。r + + 口。x 1 - a o ，( 口声o ) 是m 上无平方因子的多项式。( 注：偶特 4 四川大学硕士学位论文 征时同样有连分数展开1 4 1 ) 。记d x 是k 的整环，即f q x l 在k 中的整闭包。故有 d 。- m + 防】扣o ) 令s 印( d o ) ) 一a nd e g d ) 一甩，分别称为d o ) 的首项 系数和次数。本文约定首项系数r , c r , ) 2 ，且次数n 1 ，此时，称为k 的常数域，r a 。一1 或者f 口的生成元g 。若弹是偶数且s g i l ( d ) ) 一1 ，则称k 为 实二次函数域，否则称k 为虚二次函数域。 定理1 2 1 设k - ，五 ) ) 是一个二次函数域，其中d e g d ( x ) w n ，则无 穷素除子m 一向在k 上的分解为 ( 1 ) 当1 1 是偶数且s 印( d o ”- 1 时，。是分裂的，即m - p p 。 ( 2 ) 当玎是偶数且s 印( d 0 ) ) 一g 时，m 是惯性的，即0 0 - p 。 ( 3 ) 当厅是奇数时，m 是分歧的，即0 0 - p 2 证明：令f - 兰，则d o ) 一t - n o 。+ 口。1 f + + 口l f 纠+ a o t 4 ) - t “，( f ) ，其中， f ( t ) _ a + a n _ l t + + 口0 f na 。一0 若厅是偶数，则k - ( f ) ，k 一女( 厂( f ) ) ，且t 2 一，( f ) - t 2 一a n ( m o d t ) 。 当a 。一1 时，r 2 一f ( t ) - 口+ 1 ) 口一1 ) ( m o d t ) ，从而m 分裂。 当a 。- g 时，r 2 一f ( t ) 一t 2 一g ( m o d f ) 不可约，从而惯性。 若h 是奇数，则k - 七( 打p ) ) ，r t 2 一t f ( t ) t 2 ( m o d t ) ，从而m 分歧。 口 由定理1 2 1 知，实二次函数域有两个无限素除子，虚二次函数域只有一 个无限素除子。 无论是实二次函数域还是虚二次函数域，我们都可以把k 嵌入k 在* 的完 备域k - 。唼) p 因此，对v 口k ，有口。誊t 一，。_ o 5 i 曼a e k , a - ，。啦记a 。一m a m - 石1 ，a t + 1 h 肛l ， 则a 有连分数展开式 1 a - 口0 + a 1 + 4 2 + 1 4 3 + 简记为口- a o ，a l ，a 2 ，】。 显然，- a 。，o 。，】，b 一- l 一 1 。 经过简单计算知巾o 】lt a o 凇小掣，p o , a l , a 2 。鼍君产， 记p 。，吒，口：，口。】| 丛，p 。，q 。e g x l ，即* ，则有儿，q 。是，口i ，口。的多项式， q 一 且对任一口j 都是一次式，分母吼与口。无关。我们称堕为口的第疗个渐近值。 q 4 g c d ( 以，吼) 1 ，则称盟为a 的第n 个既约渐近值。 q 一 性质1 2 3 ( 1 ) p o - a o ，p lj a l a o + l ，以一a p 。- 1 + 以2 o 2 ) q o 一1 q l 4 l ，q - a q 。- l + 吼一2 ，o 乏2 ) ( 2 ) p 。q 。- i p 。i q 。一( 一1 ) “一，( h 1 ) ( 3 ) p 。吼一p 。2 q 。- ( - 1 ) ”a 。，o 2 ) 证明：( 1 ) 当n - o , 1 时，结论显然成立。 则 _ ( 一1 ) 扣1 故结论对n 1 成立。 ( 3 ) 由( 1 ) 和( 2 ) ，p q2 一p 。一2 q n 一0 。p 。- l + p 。2 ) q 。2 一p 。一2 qi + q 。一2 ) 一a a ( p 吼一2 - p q 。- 1 ) - ( - 0 。a 。，结论成立。 口 定理1 2 4 ( 1 ) a 的连分数展丌有限的充要条件是口c 0 ) 。 ( 2 ) 若a 隹兄o ) ，则口的连分数展开表达式唯一 证明：( 1 ) 必要性：若口的连分数展开有限，则存在某个n ，使得 a 一【a 0 ) 4 l ，口。】- 丛c o ) 充分性：若口o ) ，则存在p 口v 1 x ，使得口一詈令一i 詈i ， 毒。口一。，则有丢。p 一【旦j 留记。善，因为n l ：1 q q ，口都是多项式，故口l口l 【j 口1 川e g r ， v l 0 c o ) ，使得a 叱- c a ，则称口为拟周期 的，此时v ：一p ，的最小值m 称为口的拟周期。若h 。0 ，则称a 为纯拟周期的。 若c - 1 ，即口，：一盯，则称a 为周期的，此时y ：一h 的最小值孵称为口的周期， 记a - 【口。，五：瓦+ ，i i i ：1 。同理，若h - 0 ，则称口为纯周期的。 周期与拟周期的关系可表示成下面的定理。 定理1 3 1 1 7 1 ( 1 ) 若口的拟周期m 是奇数，则口是周期的，且周期n = m 或n = 2 m 。 ( 2 ) 若a 的拟周期t n 是偶数，则口是周期的当且仅当c 是单位根。 若c 是，次本原单位根，则周期n = r m 。 证明：假设口。i c 口，则有 o v + m + i l l c ”a ，“， 。：；= ：忑。c ( o t v - - ( i v ) 。a p “ 口r+m+：。：石1。：j：南a。c一2口r+：a m “一口m + lc ”怛v “一p j a p + 抽ic f 矿口p + m c ( 一1 r + l a r 。 若m 是奇数，则a 。i 口，从而口是周期的。若c - 1 ，则周期n i2 m ， 若c 一1 ，则周期n - m 。 8 且仅当 c 7 - 1 。若c 恰是r 次本原单位根，则周期n = r m 。 口 定理1 3 2 若a c t g ( x ) 是周期的当且仅当口是某个多项式 日( x ) - a x 2 + b x + c 的根，其中口，b ，c e f ( x ) ，且h ( x ) 在o ) 上不可约。 证明：必要性：设口- 口。，石j 磊i 磊】，则口- a ，口州，口+ 。- ，口】， 由性质1 2 3 ，口。- ! 生! 等，其中p - 扣，口，。一。】，譬- k 印，：1 。即 a # q + q qq 口a ；+ ( q p ) a 一0 ，又a p t c - t t ，u + p u - 2 ，从而a - 旦监二垃。将口_ q n z o r n q n 2 pn i q n _ , a 代入知，口一定是某个二次方程必z + 婿+ c 0 的根因为 a c g ( x ) ，a - b 2 一钿c 不是某个多项式的完全平方，所以该方程不可约。 充分性：令h ( x ，l ，) - a x 2 + b x y + c y 2 把口旦堑监代入h ( j ) 得 q 。一l c + q 一2 一。a ：+ e o n + q - 0 ，其中4 - h ( 以- l 吼1 ) ，见一2 印。- l 见一2 + 6 p 。1 q n 2 + 以弛1 ) + 2 c q 一i q n 2 ，c - 朗匕k - 2 ，吼一2 ) - 4 - 1 若4 - 0 ，则有 ) 从 而a n o ，是二次方程爿。y 2 + 玩l ，+ q - 0 的根，且研一4 以q 一( 6 2 一缸c ) 。 下面说明4 ，只，e 有界因为以。- + 亟，其中屯。生垡红， q - iq n i “a 十q n 2 i 屯- , i 。l 剁“，所以4 2 口砌。 ：_ - 童t - 乳t 于是h i t 陋口| + | 口i + 川， l c 1 - i 彳。i c l 2 口a l + h + 纠而l 彤i - 1 4 以q + p 2 一和c ) i c 帆8 c i + p 2 一和c i 。 所以以，只，e 的次数有界。由于是有限域，4 ，只，e 只有有限组取值。从而 至少有组( 4 ，玩，c ) 可对应三个，口叩口。作为a y 2 + 瓯y + c - 0 的根。 因此至少有两个相同，设- 口。：，则4 一口如，口 “一4 + i ， 口 特别的，本文所关注的扣 ) 适合方程：y 2 一o ( x ) - o ，d 0 ) 无平方因子 因此，万两是周期的。 9 li-r 。lri 四川大学硕士学位论文 第二章实二次函数域的既约理想 2 1 既约理想的定义 令k c o ，历) 足一个实二次函数域。集合口称为d x 的( 整) 理想，若 口+ 盯盯且o , a 盯。特别的，若盯- 似) a o x ，则盯称为0 k 的主理想。 定理2 1 1 设口为0 。的理想，则存在s , q ，p f , i x ，q i o p 2 ，使得 d - s o ，s e + s 4 - s l - ( s ) o ，e + 4 - 5 1 。( 记号m ，b 】表示爿嘲+ b 缸1 。) 证明：首先，d 。作为二次函数域的整环是一个d e d e k i n d 整环，从而o x 的理想 至多由两个元生成。不妨设o r - p + b 4 - 5 ，c + a 4 - 5 ，其中a , b ，c ，d 乞m 。 设g c e ( b ，d ) 一b7 ，则存在r i ，r 2 c b j ，使得机+ 奶- b ，则 口- 【口+ 6 厄( 口+ 6 伍) + p + d 伍) ，2 卜p + b 4 - d , c + 6 伍】，c 。q + c ，2 。 不妨设6 6 ，3 ，贝0 盯【( 4 + 6 4 - 5 ) 一( c + 67 石) ，3 ，c + 6 万】- p ，c + 6 4 - 5 ，其 中4 一4 一c ，r 3 。因此，盯总可以化为形式- m ，b + c , f o ，a ，b ，c k 卜 设g c d ，b ) 一j | l f 。则存在r 。，r ：e i x 】，使得m - r 一+ 尺：b ，则 口一口，m + a 2 c 4 - 5 1 不妨设a - a m ，r 2 c c ，且g c d ( m ，c ，) - ， 一r ，m + r 。c ，贝0 口一【一 ，r 4 a m + 4 4 - d 。又l m ，令a n - s ， a m s q ，r 。a m - s p ，则有盯- ( s ) q ，p + 4 - 5 。令q - g c d ( q ，p 2 一d ) ， 此时，盯- ) 【q ，p + 4 - 5 ，且q l d p 2 - 口 注：( 1 ) 若s 印p ) - s g n ( q ) 一1 ，贝1 l a 的表达式唯一。 ( 2 ) 若s 一1 ，则称口为本原理想。 ( 3 ) 若仃为本原理想，且| q jtj 历i ，则称盯是既约理想 显然a k - 【1 ，dj 是既约主理想。事实上，后面我们将看到，通过连分数展 开将得到所有与d 。等价的既约主理想。 1 0 lilr - i lii【 四j i i 大学硕士学位论文 对本原理想盯- 【q ，p + 万】，令口- p 面+ 4 一- 6 ，由第一章的讨论，我们可以 对口作连分数展开，也称为对本原理想盯作连分数展开 趣2 2 ”警，q o l d - 彳一 f - a , q i 一只- d 一 卜学峨一舡 其中d - 陋j a i 分别表示只+ d 除以q 的商式和余式，d e g r 。t d e g q ；，i 之0 ， 则有口。一1 p , + ；_ 4 5 ，q , i 。一只2 硼凇q q 珥q l + l 一学 翔“眈叩击a - 盘一警 口。一。 咒+ 、d 一口。鳊 q 1 假必叫时成立捌击a - 志。喾1 a 。一。+ 上j 一口。蜴i 靠+ 腼埘川一- 学脏 另夕h ，由p j + d 一口。q i + ，d e g r j d e g q , ，有 只“一a l q f 一层- d 一 ql“-兰三掣一ql。一口。(只+一只)一q。一(d一)一(d一-) 一q i + 口。( 一一i ) 口 由定理2 2 1 知，对一个本原理想作连分数展开可以得到一系列的本原理 相 四j i i 大学硕士学位论文 若口圣 ) 且同c l 我f f m 是既约元。因此，口- 学是既约元 的充要条件是i p 一司t i q l cp + 司。 顺2 2 1 2 【l l 舶一学雠撇跚砸忆，一譬漕q 舰纵， 则 ( 1 ) 阱h 倜一阔- p i ( 2 ) s g n ( p , ) 一s g n ( 4 - 万) ，f 1 p , ，4 - b 的次高项也相等。 ( 3 ) p 。q j l - 旧。特别的，1 c 协i 倜1 i q f | p 一忙，2 p , 3 p ，伽一1 ) p 与 由万作连分数展开得到的既约主理想k t f 。 一一对应 对应关系如下： 。一m q 一阻万j 2 p _ 0 2 ，2 )h0 2 ，y 2 ) h 吃- 肛一工2 ，_ ) ，2 + d 1 l p “，坼) 一“，y ，) 一q 一 x - - x t ，y ，+ 面】 o d p o 。，一，) 一( 。，只一。) 一。- i x - - x u 。y 。+ 万】 注：事实上，万的拟周期所一以一l 川，则作为理想来说，f 州f i + ，2 0 。 玄“h 1 ) 则称d e g ( 吼) 为仃到的距离，记为6 。或6 ( 盯，吒) 。 显然，当j 增大时，6 。也增大。喀一0 当且仅当q o r 。并且d ，墨6 。岛当 且仅当吼h i ，s f s ， o 实二次函数域上的离散对数问题就是指，任给一个既约主理想f ，求 6 ( f ，q ) 。 引理4 2 。2 4 _ d c g d - d e g q + 善d e g ( 口) 证明： 嘲n l = i i - i 丽ii | ：| l 表七旷警， 故d e g 谚+ d e g o i - d e g q 一1 - d e g q 。 又岛。l = l 玄一。所以如卿一荟o c g ( 口小 从而d e g 玩- l d e g d - d e g q + 薯d e g 。，) 利用引理4 2 2 ，既约主理想问的距离4 6 瓴，_ ) - 2 一o + 善1 - f 1 6 口 婴型盔兰堡主堂垡堡苎 定理4 2 ，3 特征3 的有限域上，可以在多项式时问内解决亏格l 的实二次函 数域上的离散对数问题当且仅当可以在多项式时间内解决j ( e ) 一0 的椭圆曲线 上的离散对数问题。 证明：必要性：在特征3 的有限域上，如果我们可以在多项式时间内解决亏格 1 的实二次函数域上的离散对数问题。设e ：w 2 v 3 + a 2 v 2 + ，a 一- a 2 a 6 0 。 有理点p 一( 口，6 ) ( e ) ，p - * 。若o r d p 一2 ，则结论是平凡的设o r d p 孝2 ， 在前面定义的双有理等价映射下，有e ，：y 2 。一+ a 2 x 2 + b x + a a ，+ 口；一d 。对 d 作连分数展开后可以得到所有的既约主理想，记为t i t - b , 4 - 5 ，屯，令 q e e ( f g ) ，q i p ，2 ，o r d p ，若f o r d p ，则q 一，对应既约主理想。若 q - m ，p ，则q 对应功- x - x q ，蜘+ 五卜_ ，而e ，e ，的双有理等价关系可 以在多项式时间内算出，由假设，1 4 - ( r i ，) 可在多项式时间内算出。 充分性：如果我们可以在多项式时间内解决( e ) 一0 的椭圆曲线的离散对 数问题。设k 一只o ，4 5 ) 是亏格等于1 的实二次函数域，d 无平方因子，不妨 设d - 工4 + a 2 x 2 + 撅+ 4 口2 + 口；，a , b ，c e f , 。令耳：) ，2 - d ，则由双有理等价映射 有e ：，2 一v 3 + 口：v 2 + 口。及点p ( 4 ，6 ) e ( ) 、p 。记_ 一阻万】，乇，如上 所述，若f t ，if - 一+ l ，则结论是平凡的。若f q ，2 ，掰，我 们可以在多项式时间内把f 表为f - 防+ e ，+ d 】，p ，f e e , 。由此，f 对应e p 上 的点q 一( 叩，厂) ，而我们又可以在多项式时间内再把e ，上的点q 换为e 上的点 q 。故由假设，6 p ，) 一f 可在多项式时间内求出。 口 1 7 | _ 四川大学硕士学位论文 参考文献 【1 】a s t e i n ，e q u i v a l e n c e s b e t w e e n e l l i p t i c c u r v e s a n d r e a l q u a d r a t i c c o n g r u e n c e f u n c t i o n f i e l d s ，j o u r n a ld et h e o r l ed e sh o m b r e sd eb o r d e a u x ，9 ( 1 9 9 7 ) , 7 5 9 5 【2 】a s t e i n ，h c w i l l i a m s ，b a 印s t e pg i a n ts t e pi nr e a lq u a d r a t i cf u n c t i o nf i e l d s ， a v a i l a b l ea tf t p ：v i e t a m a t h u n i s b d e p u b s i m a t h a n d r e a s - s t e i n b g p s 9 2 【3 1 d s h a n k s , t h e i n f r a s t r u c t u r e o f a r e a l q u a d r a t i c f i e l d a n d i t s a p p l i c a t i o n s p r o c 1 9 7 2 n u m b e rt h e o r yc o n f b o u l d e r , c o l o r a d o ，1 9 7 2 , 2 1 7 - 2 2 4 【4 】j z r o b e r t , t h ee q u i v a l e n c eb e t w