LLL算法的衍生算法及其应用研究

发布时间：2017-07-05 13:11

  本文关键词：LLL算法的衍生算法及其应用研究

  更多相关文章： LLL算法 格理论 有限域 分圆多项式 不可约多项式

【摘要】：本文分为两个部分。第一部分详细介绍了LLL算法及其应用。1982年,A.K.Lenstra, H.W.Lenstra.Jr, L.Lovasz提出了LLL算法,由于在实际应用中收到了很好的效果和广泛的应用,并且十分简明,LLL算法立即引起了很大的关注,它被认为是有关NP问题的一大突破,并被认为是20世纪最重要的算法成果之一。在LLL算法启发下,出现了很多更快更好的算法,对计算机代数、密码学、算法数论等领域产生了重要的推动作用。本文第一部分从LLL算法的思想、算法时间复杂度、算法的衍生改进算法以及算法在不同领域中的应用等几个方面对LLL算法进行了介绍。 本文的第二部分讨论了有限域上3nr次分圆多项式的分解,证明了对于3nr次分圆多项式,其所有不可约因式都可以由同样类型的分圆多项式的不可约因式得到,并且作为这个方法的示例,给出了3n次以及3n·5次的分圆多项式的分解。
【关键词】：LLL算法 格理论 有限域 分圆多项式 不可约多项式
【学位授予单位】：北方工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O153.1
【目录】：

• 摘要3-4
• ABSTRACT4-6
• 第一章 格理论与格基规约问题6-11
• 1.1. 格理论6-8
• 1.2. 格理论中的计算难题和LLL算法的提出背景8-11
• 第二章 LLL的思想和复杂度分析11-19
• 2.1. LLL约减基11-13
• 2.2. LLL算法的思想13-14
• 2.3. 复杂性分析14-19
• 第三章 LLL算法的改进算法和应用19-30
• 3.1 深插方法19
• 3.2. 分组Korkin-Zplotarev约减法19-20
• 3.3. 最近平面算法20-22
• 3.4. LLL算法在数论中的应用22-26
• 3.4.1. LLL算法在丢番图逼近中的应用22-25
• 3.4.2. LLL算法在整线性相关问题中的应用25-26
• 3.4.3. 对数论中猜想的验证26
• 3.5. 攻击低公钥指数RSA密码26-27
• 3.6. LLL算法在整数规划中的应用27-30
• 第四章 有限域基础30-37
• 4.1. 有限域上的基本结果30-32
• 4.2. 有限域上的多项式32-37
• 4.2.1. 有限域上多项式的阶32-33
• 4.2.2. 分圆多项式33-35
• 4.2.3. 合成和与合成积35-37
• 第五章 有限域上分圆多项式的分解37-42
• 5.1. 3n型分圆多项式的分解37-39
• 5.2. 3nr型分圆多项式的分解39-42
• 第六章 总结42-43
• 参考文献43-45
• 申请学位期间的研究成果及发表的学术论文45-46
• 致谢46

【参考文献】

中国期刊全文数据库 前1条

1 肖鸿,赵惠文;格基归约在密码上的应用[J];西安电子科技大学学报;2000年06期

，

本文编号：522090