学位论文 > 优秀研究生学位论文题录展示

对GHS算法的分析

作　者: 谌昭
导　师: 印林生
学　校: 清华大学
专　业: 基础数学
关键词: 椭圆曲线离散对数问题韦依下降 GHS算法
分类号: O182.1
类　型: 硕士论文
年　份: 2013年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

2001年，P. Gaudry，F. Hess，N. P.Smart等三个人利用G. Fray的思想给出了GHS算法[1],即把椭圆曲线（或者超椭圆曲线）上的离散对数问题转化到更小的域上更高亏格的曲线上的离散对数问题，算法的复杂度与扩张次数以及后来曲线的亏格有关。这是特征为2的有限域上的椭圆曲线离散对数问题最好的算法。在文中他们提出了一个椭圆曲线可以使用GHS算法的充分条件，但不是必要条件，并且说明不满足这个条件的椭圆曲线不会很多。在本文中，我得到了判断椭圆曲线可否使用GHS算法的一个充要条件，并且在给出适当的定义的基础上我使这个充要条件可以用于计算。然后我们给出了一个不等式，通过这个不等式我们可以估算出到底有多少椭圆曲线不满足原有充分条件但却满足我们的充要条件，并且这个不等式也可以给出在GHS算法下危险的椭圆曲线数量的一个上界。此后我们针对不同的条件对椭圆曲线所占比例以及计算复杂度作了举例分析，我们给出的充要条件相对原条件确实扩展了GHS算法的适用范围。

全文目录

摘要  3-4
Abstract  4-8
第1章选题背景  8-11
  1.1 问题来源  8
  1.2 研究问题的历史  8-9
  1.3 GHS攻击的主要结论  9-11
第2章本文主要结论  11-13
第3章 GHS算法的主要过程  13-17
  3.1 覆盖攻击  13-14
  3.2 韦依下降  14
  3.3 变换到超椭圆函数域  14-17
第4章结论的证明  17-21
  4.1 定理2.1的证明  17
  4.2 定理2.2的证明  17-18
  4.3 定理2.3的证明  18-20
  4.4 推论2.1的证明  20-21
第5章算法分析  21-24
  5.1 n是奇数  21-22
  5.2 n是偶数且a的迹等于0  22
  5.3 n是偶数且a的迹等于1，m=n  22
  5.4 n是偶数且a的迹等于1，j0= 2~u  22-24
第6章举例分析  24-29
  6.1 GHS算法失败的情形  24-25
  6.2 GHS算法成功的情形  25-29
    6.2.1 n是奇数时  26
    6.2.2 n是偶数且a的迹为0时  26-27
    6.2.3 n是偶数且a的迹等于1，m=n  27
    6.2.4 n是偶数且a的迹等于1  27-29
第7章总结  29-30
参考文献  30-31
附录A 大步-小步法和指标计算方法  31-33
  A.1 大步-小步法  31
  A.2 指标计算方法  31-33
附录B F_2上x~n-1的分解  33-34
致谢  34-36
个人简历、在学期间发表的学术论文与研究成果  36

对GHS算法的分析

内容摘要

全文目录

相似论文